Cod sursa(job #1005758)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 5 octombrie 2013 18:37:13
Problema Rsir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

class RSir {
public:
  RSir(int e0, int e1, int a, int b, int c, int x, int y, int m) {
    t0 = e0, t1 = e1;
    a1 = a, b1 = b, c1 = c;
    a2 = x, b2 = y;
    mod = m;

    preprocess();
  }

  int t(long long n) {
    if (n == 0) return t0;
    if (n == 1) return t1;

    pair<int, int> v1(t0 % mod, t1 % mod);
    pair<int, int> v2(v1);

    if (n < 1000000) {
      for (int i = 1; i < n; ++i) v1 = next(v1);
      return v1.second;
    }

    int index = 1;
    do {
      index += 1;
      v1 = next(v1);
      v2 = next(next(v2));
    } while (v1 != v2);

    n = (n - index) % (index - 1);
    for (int i = 0; i < n; ++i) v1 = next(v1);
    return v1.second;
  }

private:
  int t0, t1;
  int a1, b1, c1;
  int a2, b2;
  int mod;

  pair<int, int> next(pair<int, int> vals) {
    int val = p[0][vals.first] + p[1][vals.second];
    if (val >= mod) val -= mod;
    return make_pair(vals.second, val);
  }

  void preprocess() {
    p[0].resize(mod);
    p[1].resize(mod);

    for (int i = 0; i < mod; ++i) {
      p[0][i] = (((i * i) % mod) * a1 + i * b1 + c1) % mod;
      p[1][i] = (((i * i) % mod) * a2 + i * b2) % mod;
    }
  }
  vector<int> p[2];
};

int main() {
  ifstream fin("rsir.in");
  ofstream fout("rsir.out");
  int T0, T1, a, b, x, y, z, MOD;
  fin >> T0 >> T1 >> a >> b >> x >> y >> z >> MOD;
  RSir solve(T0, T1, a, x, z, b, y, MOD);
  long long N;
  fin >> N;
  fout << solve.t(N);
}