Cod sursa(job #2059291)

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

using namespace std;

FILE *f, *g;

typedef long long lint;

int rez;

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

int t0, t1;
int MOD, 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, "%d%d", &a, &b);
    fscanf(f, "%d%d%d", &x, &y, &z);
    fscanf(f, "%d%d", &MOD, &n);

    fclose(f);
}

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

    cr = {(int)n0, (int)n1};
}

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

    int ramas = n - 1;
    int luat = 1;
    elem cr = {t0, t1};
    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;
}