Cod sursa(job #1420110)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 17 aprilie 2015 16:54:51
Problema Rsir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <fstream>
#include <utility>

#define MMAX 7005
#define lint long long int
using namespace std;

int mod;
int prec1[MMAX];
int prec2[MMAX];

inline void _next (pair <int, int> &_pair) {
    int aux = prec1[_pair.first] + prec2[_pair.second];
    if (aux >= mod)
        aux -= mod;

    _pair.first = _pair.second;
    _pair.second = aux;
}

int main()
{
    ifstream cin("rsir.in");
    ofstream cout("rsir.out");

    int t0, t1, a, b, x, y, z;
    lint n = 0;

    cin >> t0 >> t1 >> a >> b >> x >> y >> z >> mod >> n;

    if (!n) {
        cout << t0 << '\n';

        cin.close();
        cout.close();
        return 0;
    }
    n--;

    for (int i = 0; i < mod; i++) {
        prec1[i] = (i * ((i * a + x) % mod) + z) % mod;
        prec2[i] = (i * ((i * b + y) % mod)) % mod;
    }

    pair <int, int> t = make_pair(t0, t1), h = make_pair(t0, t1);
    do {
        _next(t);
        _next(h); _next(h);
    } while (t != h);

    int tail = 0;

    t = make_pair(t0, t1);
    while (t != h) {
        _next(t);
        _next(h);

        tail ++;
    }

    int cycle = 1;

    _next(t);
    while (t != h) {
        _next(t);

        cycle ++;
    }

    if (n < tail) {
        t = make_pair(t0, t1);

        for (int i = 0; i < n; i++)
            _next(t);

        cout << t.second << '\n';

        cin.close();
        cout.close();
        return 0;
    }

    n -= tail;
    n %= cycle;

    for (int i = 0; i < n; i++)
        _next(h);

    cout << h.second << '\n';

    cin.close();
    cout.close();
    return 0;
}