Cod sursa(job #2059300)

Utilizator Coroian_DavidCoroian David Coroian_David Data 6 noiembrie 2017 20:59:22
Problema Rsir Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <bits/stdc++.h>

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;

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);

    fclose(f);
}

void adv(elem &cr)
{
    lint n0, n1;
    lint t0 = 1LL * cr.t0;
    lint t1 = 1LL * cr.t1;
    n0 = cr.t1;
    n1 = (a * t0 * t0 + b * t1 * t1 + x * t0 + y * t1 + z) % (MOD);

    int ni0 = (int)n0;
    int ni1 = (int)n1;

    cr = {ni0, ni1};
}

void solve()
{
    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;
}