Cod sursa(job #1646793)

Utilizator sebinechitasebi nechita sebinechita Data 10 martie 2016 17:46:11
Problema Rsir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rsir.in");
ofstream fout("rsir.out");
#define MAX 7010
#define cout fout
int a, b, x, y, z, m;
long long n, ccn;
int number[MAX][2], square[MAX][2];
int ar(int n)
{
    while(n >= m)
        n -= m;
    return n;
}

pair<int, int> get_next(pair<int, int> t)
{
    return make_pair(t.second, ar(square[t.first][0] + square[t.second][1] + number[t.first][0] + number[t.second][1] + z));
}

void precalc()
{
    for(int i = 0 ; i < m ; i++)
    {
        square[i][0] = (a * ((i * i) % m)) % m;
        square[i][1] = (b * ((i * i) % m)) % m;
        number[i][0] = (x * i) % m;
        number[i][1] = (y * i) % m;
    }
}

pair<int, int> rez(pair<int, int> t, long long n)
{
    for(int i = 2 ; i <= n ; i++)
        t = get_next(t);
    return t;
}

int main()
{
    int i, j, cn;
    pair<int, int> t, t2, ct;
    fin >> t.first >> t.second >> a >> b >> x >> y >> z >> m >> n;
    precalc();
    t.first %= m;
    t.second %= m;
    ct = t;
    ccn = n;
    t2 = t;
    if(n <= m * m + 100)
    {
        cout << rez(t, n).second;
        return 0;
    }

    t = rez(t, 1ll * m * m);
    //cout << "!!";
    n -= m * m;
    t2 = t;
    for(j = 1 ; ; j++)
    {
        t = get_next(t);
        if(t == t2)
            break;
    }
    cn = n % j;
    for(i = 1 ; i <= cn ; i++)
        t = get_next(t);

    cout << t.second;
}