Cod sursa(job #1289440)

Utilizator diana97Diana Ghinea diana97 Data 9 decembrie 2014 21:27:17
Problema Rsir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("rsir.in");
ofstream g ("rsir.out");

const int MMAX = 7000 + 1;

int T0, T1, a, b, x, y, z, mod;
long long n;
int x1[MMAX], x2[MMAX];

void citeste() {
    f >> T0 >> T1 >> a >> b >> x >> y >> z >> mod >> n;
}

pair <int, int> termenul_urmator(pair <int, int> p)
{
    int urm = x1[p.first] + x2[p.second];
    if (urm >= mod) urm-= mod;
    return make_pair(p.second, urm);
}

void rezolva() {
    T0 %= mod;
    T1 %= mod;
    for (int i = 0; i <= mod; i++) {
        x1[i] = (1LL * a * i * i + x * i + z) % mod;
        x2[i] = (1LL * b * i * i + y * i) % mod;
    }

    bool done;
    long long nr1 = 0, nr2 = 0;
    pair <int, int> p1, p2;

    p1 = p2 = make_pair(T0, T1);
    done = false;
    while (!done) {
        nr1++;
        if (n == nr1) {
            g << p1.second;
            return;
        }
        p1 = termenul_urmator(p1);
        p2 = termenul_urmator(termenul_urmator(p2));
        if (p1 == p2) done = true;
    }

    done = false;
    while(!done) {
        nr2++;
        p1 = termenul_urmator(p1);
        if (p1 == p2) done = true;

    }

    n = (n - nr1) % nr2;
    if (!n) n += nr2;
    for (int i = 2; i <= n; i++) p1 = termenul_urmator(p1);
    g << p1.second;
}

int main() {
    citeste();
    rezolva();
    return 0;
}