Cod sursa(job #2770833)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 23 august 2021 16:40:49
Problema Rsir Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("rsir.in");
ofstream out("rsir.out");

using ll = long long;

const int maxN = 7000;

ll n;

int a, b, x, y, z, m, t1, t0;

int h1[maxN + 5], h2[maxN + 5];

pair<int, int> getNext(pair<int, int> now) {
  /// now = {now.first, now.second}
  ///         n - 2        n - 1
  pair<int, int> nxt = make_pair(now.second, 0);
  nxt.second = h1[now.first] + h2[now.second] + z;
  while (nxt.second >= m) {
    nxt.second -= m;
  }
  return nxt;
}

int main() {
  in >> t0 >> t1 >> a >> b >> x >> y >> z >> m >> n;
  t0 %= m;
  t1 %= m;
  a %= m;
  b %= m;
  x %= m;
  y %= m;
  z %= m;
  for (int i = 0; i < m; i++) {
    h1[i] = (1LL * i * i * a + i * x) % m;
    h2[i] = (1LL * i * i * b + i * y) % m;
    assert(h1[i] >= 0 && h2[i] >= 0);
  }
  pair<int, int> t = make_pair(t0, t1);
  pair<int, int> h = make_pair(t1, getNext(t).second);
  while (t != h) {
    t = getNext(t);
    h = getNext(getNext(h));
  }
  t = make_pair(t0, t1);
  h = getNext(h);
  int start = 0;
  while (t != h) {
    t = getNext(t);
    h = getNext(h);
    start++;
  }
  int len = 1;
  h = getNext(t);
  while (h != t) {
    h = getNext(h);
    len++;
  }
  cerr << start << " " << len << "\n";
  if (n <= start) {
    if (n > 0) {
      pair<int, int> now = make_pair(t0, t1);
      for (int i = 2; i <= n; i++) {
        now = getNext(now);
      }
      out << now.second << "\n";
    } else {
      out << t0 << "\n";
    }
  } else {
    n -= start;
    n %= len;
    if (n == 0) {
      n = len;
    }
    pair<int, int> now = h;
    for (int i = 2; i <= n; i++) {
      now = getNext(now);
    }
    out << now.second << "\n";
  }
  return 0;
}