Cod sursa(job #919197)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 19 martie 2013 14:49:58
Problema Rsir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
#define t0 first
#define t1 second
#define MM 7010
 
using namespace std;
 
ifstream f("rsir.in");
ofstream g("rsir.out");
 
typedef pair<int, int> PI;
int a, b, x, y, z;
int M;
long long N;
int i, j;
int CA[MM], CB[MM];
int T0, T1;
 
void Advance (PI& S)
{
    S=make_pair(S.t1, CA[S.t0]+CB[S.t1]);
    if (S.t1>=M) S.t1-=M;
}
 
int main ()
{
    f >> T0 >> T1 >> a >> b >> x >> y >> z >> M >> N;
 
    T0%=M;
    T1%=M;
 
    for (i=0; i<M; i++)
    {
        CA[i]=(1LL*a*i*i+x*i+z)%M;
        CB[i]=(1LL*b*i*i+y*i)%M;
    }
 
    PI Slow=make_pair(T0, T1), Fast=Slow;
    int Steps=0, CycleL=0, Queue=0;
 
    do
    {
        Advance(Slow);
        Advance(Fast);
        Advance(Fast);
        ++Steps;
    } while (Slow!=Fast);
 
    Fast=make_pair(T0, T1);
 
    while (Fast!=Slow)
    {
        Advance(Fast);
        Advance(Slow);
        ++Steps;
        ++Queue;
    }
 
    CycleL=Steps-Queue;
 
    if (N==0)
    {
        g << T0 << '\n';
 
        f.close();
        g.close();
 
        return 0;
    }
 
    if (N>Queue)
    {
        N=Queue+(N-Queue)%(1LL*CycleL);
        if (N==Queue) N+=CycleL;
    }
 
    Slow=make_pair(T0, T1);
 
    for (i=1; i<N; i++)
        Advance(Slow);
 
    g << Slow.second << '\n';
 
    f.close();
    g.close();
 
    return 0;
}