Cod sursa(job #2159115)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 10 martie 2018 19:14:53
Problema Rsir Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#include <set>

using namespace std;

long long t0, t1, a, b, x, y, z;
long long m, n;

long long GetNext()
{
    long long ret = (a * t0 * t0 + b * t1 * t1 + x * t0 + y * t1 + z) % m;
    t0 = t1;
    t1 = ret;
    return ret;
}

int main()
{

    ifstream in("rsir.in");
    ofstream out("rsir.out");
    in >> t0 >> t1 >> a >> b >> x >> y >> z;
    in >> m >> n;
    t0 %= m, t1 %= m;
    long long copyT0 = t0, copyT1 = t1;
    in.close();
    if(n < 5e7)
    {
        if(n == 0)
            out << t0;
        else if(n == 1)
            out << t1;
        else
        {
            long long rasp;
            for(long long i = 2; i <= n; ++i)
                rasp = GetNext();
            out << rasp;
        }
        return 0;
    }
    long long startPeriod[2];
    long long periodPos = -1;

    long long ind = 2, current = t1, last;
    for(long long i = 0; i < m * m; ++i)
    {
        last = current; //v[ind-1] = last
        current = GetNext(); //v[ind] = current;

        if(last == copyT0 && current == copyT1)
        {
            startPeriod[0] = last;
            startPeriod[1] = current;
            periodPos = ind;
            break;
        }
        ind++;
    }

    long long first = 1;
    t0 = copyT0, t1 = copyT1;

    long long periodSize = periodPos - first;
    long long remain = (n - first + 1) % periodSize;
    if(remain == 0)
        remain = periodSize - 1;
    else
        remain--;
    long long rasp = current;
    while(remain--)
        rasp = GetNext();

    out << rasp;
    out.close();
    return 0;
}