Cod sursa(job #2193045)

Utilizator cella.florescuCella Florescu cella.florescu Data 8 aprilie 2018 15:03:44
Problema Rsir Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXM = 7e3;
typedef pair < int, int > PII;

int amod[MAXM], bmod[MAXM], xmod[MAXM], ymod[MAXM], z, m;

inline PII nxt(PII x) {
  int aux = amod[x.first] + bmod[x.second] + xmod[x.first] + ymod[x.second] + z;
  while (aux >= m)
    aux -= m;
  return {x.second, aux};
}

int main()
{
    int t0, t1, a, b, x, y;
    long long n;
    ifstream fin("rsir.in");
    fin >> t0 >> t1 >> a >> b >> x >> y >> z >> m >> n;
    fin.close();
    t0 %= m; t1 %= m; a %= m; b %= m; x %= m; y %= m; z %= m;
    for (int i = 0; i < m; ++i) {
      amod[i] = 1LL * a * i * i % m;
      bmod[i] = 1LL * b * i * i % m;
      xmod[i] = x * i % m;
      ymod[i] = y * i % m;
    }
    ofstream fout("rsir.out");
    if (n == 0) {
      fout << t0;
    } else if (n == 1) {
      fout << t1;
    } else {
      PII p1 = {t0, t1}, p2 = {t0, t1};
      do {
        p1 = nxt(p1);
        p2 = nxt(nxt(p2));
      } while (p1 != p2);
      int lcyc = 0;
      do {
        p1 = nxt(p1);
        ++lcyc;
      } while (p1 != p2);
      p1 = p2 = {t0, t1};
      for (int i = 0; i < lcyc; ++i)
        p2 = nxt(p2);
      int lchain = 0;
      while (p1 != p2) {
        ++lchain;
        p1 = nxt(p1);
        p2 = nxt(p2);
      }
      if (n > lchain)
        n = lchain + (n - lchain) % lcyc;
      p1 = {t0, t1};
      for (int i = 1; i < n; ++i)
        p1 = nxt(p1);
      fout << p1.second << '\n';
    }
    fout.close();
    return 0;
}