Cod sursa(job #795869)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 9 octombrie 2012 19:47:19
Problema Rsir Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstdio>
#include <algorithm>
#include <cassert>

#define t0 first
#define t1 second

using namespace std;

typedef pair<int, int> pii;
typedef long long LL;

const int MaxM = 7005;

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

inline int Mod(int Value) {
    if (Value >= M)
        Value -= M;
    return Value;
}

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

inline void Advance(pii &T) {
    T = make_pair(T.t1, Mod(A[T.t0]+B[T.t1]));
}

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

inline int Query(LL N) {
    if (N == 0)
        return T0;
    if (N == 1)
        return T1;
    pii 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() {
    assert(freopen("rsir.in", "r", stdin));
    assert(scanf("%d %d %d %d %d %d %d %d %lld", &T0, &T1, &a, &b, &x, &y, &z, &M, &n) == 9);
    T0 %= M, T1 %= M;
}



void Print() {
    assert(freopen("rsir.out", "w", stdout));
    printf("%d\n", Query(n));
}

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