Cod sursa(job #1331556)

Utilizator smaraldaSmaranda Dinu smaralda Data 31 ianuarie 2015 20:02:43
Problema Rsir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define LL long long
const int MMAX = 7005;

pair <int, int> turtle, hare;
int a, b, x, y, z, t0, t1, m, mod0[MMAX], mod1[MMAX];

inline pair <int, int> next (pair <int, int> t) {
    int x = mod0[t.first] + mod1[t.second];
    if(x >= m)
        x -= m;
    return make_pair(t.second, x);
}

int main() {
    freopen("rsir.in", "r", stdin);
    freopen("rsir.out", "w", stdout);
    int i, len, nSteps;
    LL n;

    scanf("%d%d%d%d%d%d%d%d%lld", &t0, &t1, &a, &b, &x, &y, &z, &m, &n);

    for(i = 0; i < m; ++ i) {
        mod0[i] = ((LL)a * i * i + x * i + z) % m;
        mod1[i] = ((LL)b * i * i + y * i) % m;
    }

    turtle = hare = make_pair(t0 % m, t1 % m);
    nSteps = 0;
    do {
        ++ nSteps;
        if(nSteps == n) {
            printf("%d\n", turtle.second);
            return 0;
        }

        turtle = next(turtle);
        hare = next(next(hare));
    }while(turtle != hare);


    len = 0;
    do {
        ++ len;
        turtle = next(turtle);
    }while(turtle != hare);

    n = (n - nSteps) % len;
    if(n == 0)
        n = len;

    for(i = 2; i <= n; ++ i)
        turtle = next(turtle);

    printf("%d\n", turtle.second);
    return 0;
}