Cod sursa(job #855301)

Utilizator danalex97Dan H Alexandru danalex97 Data 14 ianuarie 2013 20:56:14
Problema Rsir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <algorithm>
using namespace std;

typedef pair<short, short> Pair;
#define t0 first
#define t1 second
#define mp make_pair

typedef long long I64;

ifstream F("rsir.in");
ofstream G("rsir.out");

const int Mmax = 7010;

short T0,T1,M;
short A[Mmax],B[Mmax];

int Ciclu;
Pair X;

int a,b,x,y,z;
I64 N;

void next(Pair &T)
{
    T = mp(T.t1, A[T.t0]+B[T.t1]);
    if (T.t1 >= M) T.t1 -= M;
}

void Turtle_Rabbit()
{
    Pair Turtle(T0, T1), Rabbit(T0, T1);

    next(Turtle);
    next(Rabbit);
    next(Rabbit);
    while ( Turtle != Rabbit )
    {
        next(Turtle);
        next(Rabbit);
        next(Rabbit);
    }

    X = Turtle;

    next(Rabbit);
    ++Ciclu;
    while ( Turtle != Rabbit )
    {
        next(Rabbit);
        ++Ciclu;
    }
}

short Query()
{
    if (N == 0) return T0;
    if (N == 1) return T1;
    Pair T(T0, T1);

    for (; N > 1 && T != X; --N, next(T));
    if (N > 1) N %= Ciclu;
    for (; N > 1; --N, next(T));

    return T.t1;
}

int main()
{
    F>>T0>>T1;

    F>>a>>b>>x>>y>>z;
    F>>M>>N;

    T0 %= M;
    T1 %= M;

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

    Turtle_Rabbit();

    G<<Query()<<"\n";
}