Cod sursa(job #795876)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 9 octombrie 2012 20:00:33
Problema Rsir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <algorithm>

#define t0 first
#define t1 second

using namespace std;

typedef pair<short, short> Node;
typedef long long LL;

const int MaxM = 7005;

int a, b, x, y, z;
short T0, T1, M, A[MaxM], B[MaxM];
int CycleLen;
Node X;
LL n;

void Preprocess() {
    for (int i = 0; i < M; ++i) {
        int j = (i*i)%M;
        A[i] = (a*j + x*i) % M, B[i] = (b*j + y*i + z) % M;
    }
}

inline void Advance(Node &T) {
    T = make_pair(T.t1, A[T.t0]+B[T.t1]);
    if (T.t1 >= M)
        T.t1 -= M;
}

void FindCycle() {
    Node Slow(T0, T1), Fast(T0, T1);
    do {
        Advance(Slow), Advance(Fast), Advance(Fast);
    } while (Slow != Fast);
    X = Slow;
    do {
        Advance(Fast), ++CycleLen;
    } while (Slow != Fast);
}

inline short Query(LL N) {
    if (N == 0)
        return T0;
    if (N == 1)
        return T1;
    Node T(T0, T1);
    for (; N > 1 && T != X; --N, Advance(T));
    if (N > 1)
        N %= CycleLen;
    for (; N > 1; --N, Advance(T));
    return T.t1;
}

void Solve() {
    Preprocess();
    FindCycle();
}

void Read() {
    ifstream fin("rsir.in");
    int t0, t1;
    fin >> t0 >> t1 >> a >> b >> x >> y >> z >> M >> n;
    T0 = t0 % M, T1 = t1 % M;
    fin.close();
}



void Print() {
    ofstream fout("rsir.out");
    fout << Query(n) << "\n";
    fout.close();
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}