Cod sursa(job #2275847)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 3 noiembrie 2018 17:56:56
Problema Rsir Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<bits/stdc++.h>
using namespace std;

int t0,t1,a,b,x,y,z,m;

int cyc,lch;
long long n;
int f1[7005],f2[7005];
pair<int,int> nxt(pair<int,int> p)
{
    int nx=(f1[p.first]+f2[p.second])%m;
    return make_pair(p.second,nx);
}
int main()
{
    freopen("rsir.in","r",stdin);
    freopen("rsir.out","w",stdout);

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

    t0%=m;
    t1%=m;
    a%=m;
    b%=m;
    x%=m;
    y%=m;
    z%=m;

    for(int i=0;i<m;i++)
    {
        f1[i]=((a*i*i)%m+x*i)%m;
        f2[i]=((b*i*i+y)%m*i+z)%m;
    }
    if(!n)
    {
        printf("%d\n",t0);
        return 0;
    }

    if(n==1)
    {
        printf("%d\n",t1);
        return 0;
    }

    pair<int,int> p1,p2;
    p1={t0,t1};
    p2={t0,t1};

    do
    {
        p1=nxt(p1);
        p2=nxt(nxt(p2));

    }while(p1!=p2);


    do
    {
        p1=nxt(p1);
        cyc++;
    }while(p1!=p2);


    p1=p2={t0,t1};


    for(int i=0;i<cyc;i++)
        p2=nxt(p2);


    int lch=0;
    while(p1!=p2)
    {
        ++lch;
        p1=nxt(p1);
        p2=nxt(p2);
    }

    if(n>lch) n=lch+(n-lch)%cyc;

    pair<int,int> sol={t0,t1};
    for(int i=1;i<n;i++)
        sol=nxt(sol);
    printf("%d\n",sol.second);


    return 0;
}