Cod sursa(job #1093573)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 28 ianuarie 2014 11:48:25
Problema Rsir Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#include <algorithm>

#define x first
#define y second
#define NMAX 7007

using namespace std;

pair< int, int > Pointer1, Pointer2;
int a, b, x, y, z, M, n;
int A[NMAX], B[NMAX];

pair< int, int > Next(pair< int, int > P){ /// P = Pointer
    return make_pair(P.y, (A[P.x] + B[P.y]) % M);
}

int main(){
    pair< int, int > P;
    freopen("rsir.in", "r", stdin);
    freopen("rsir.out", "w", stdout);
    scanf("%d %d %d %d %d %d %d %d %d", &P.x, &P.y, &a, &b, &x, &y, &z, &M, &n);
    if(n == 0){
        printf("%d\n", P.x);
        return 0;
    }
    if(n == 1){
        printf("%d\n", P.y);
        return 0;
    }
    P.x %= M;
    P.y %= M;
    for(int i = 0; i < M; ++i){
        int k = (i * i) % M;
        A[i] = (a * k + x * i) % M;
        B[i] = (b * k + y * i + z) % M;
    }
    pair< int, int > T = P, R = P;/// T = turtle, R = rabbit
    R = Next(Next(R));
    T = Next(T);
    while(R != T){
        R = Next(Next(R));
        T = Next(T);
    }
    pair< int, int > Cicle = T;/// Cicle face parte din ciclu
    int Ciclu = 1;
    R = Next(R);
    while(T != R){
        ++ Ciclu;
        R = Next(R);
    }
    while(n > 1 && T != Cicle)
        T = Next(T);
    if(n > 1)
        n %= Ciclu;
    while(n > 1){
        -- n;
        T = Next(T);
    }
    printf("%d", T.y);
    return 0;
}