Cod sursa(job #2059498)

Utilizator Coroian_DavidCoroian David Coroian_David Data 7 noiembrie 2017 09:21:49
Problema Rsir Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <bits/stdc++.h>

#define MAX_M 7000

using namespace std;

FILE *f, *g;

typedef long long lint;

int rez;

lint a, b;
lint x, y, z;

int t0, t1;
lint MOD;
lint n;

int iMOD;

int p1[MAX_M + 1];
int p2[MAX_M + 1];

struct elem
{
    int t0, t1;

    bool operator != (const elem &a) const
    {
        return (!(t0 == a.t0 && t1 == a.t1));
    }
};

void readFile()
{
    f = fopen("rsir.in", "r");

    fscanf(f, "%d%d", &t0, &t1);
    fscanf(f, "%lld%lld", &a, &b);
    fscanf(f, "%lld%lld%lld", &x, &y, &z);
    fscanf(f, "%lld", &MOD);
    fscanf(f, "%lld", &n);

    iMOD = (int)MOD;

    fclose(f);
}

void adv(elem &cr)
{
    int n0, n1;
    int t0 = cr.t0;
    int t1 = cr.t1;

    n0 = t1;
    n1 = p1[t0] + p2[t1];

    while(n1 >= iMOD)
        n1 -= iMOD;

    cr = {n0, n1};
}

void preCalc()
{
    p1[0] = p2[0] = 0;

    int iMOD = (int)MOD;
    int i;
    lint nxt;
    for(i = 1; i < iMOD; i ++)
    {
        nxt = a * i * i + x * i;
        nxt %= MOD;

        p1[i] = (int)nxt;

        nxt = b * i * i + y * i + z;
        nxt %= MOD;

        p2[i] = (int)nxt;
    }
}

void solve()
{
    preCalc();

    t0 %= MOD;
    t1 %= MOD;

    if(n == 0)
    {
        rez = t0;

        return;
    }

    if(n == 1)
    {
        rez = t1;

        return;
    }

    ///iepure, testoasa, 2 pasi, 1 pas, intersectie = len ciclu;
    elem iep;
    elem tes;

    tes = {t0, t1};
    iep = {t0, t1};

    do
    {
        adv(tes);

        adv(iep);
        adv(iep);
    }
    while(tes != iep);

    adv(tes);
    int len = 1;

    while(tes != iep)
    {
        len ++;
        adv(tes);
    }

    ///testoasa, testoasa 2 porneste de la len ciclu => intalnire la momentu intrarii in ciclu;
    int coada = 0;
    tes = {t0, t1};
    elem tes2 = {t0, t1};

    for(int i = 1; i <= len; i ++)
        adv(tes2);

    while(tes != tes2)
    {
        coada ++;

        adv(tes);
        adv(tes2);
    }

    lint ramas = n - 1;
    int luat = 1;
    elem cr = {t0, t1};

    if(1LL * coada <= ramas)
    {
        cr = tes;
        luat = coada;
        ramas -= coada;
    }

    while(ramas > 0 && luat <= coada)
    {
        adv(cr);

        ramas --;
        luat ++;
    }

    ramas %= len;
    while(ramas > 0)
    {
        adv(cr);

        ramas --;
    }

    rez = cr.t1;

    //cout << len << " " << coada << "\n";
}

void printFile()
{
    g = fopen("rsir.out", "w");

    fprintf(g, "%d\n", rez);

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}