Cod sursa(job #1639387)

Utilizator dariusdariusMarian Darius dariusdarius Data 8 martie 2016 12:05:52
Problema Rsir Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <algorithm>
#include <fstream>
#include <iostream>
using namespace std;

int a, b, x, y, z, t0, t1, MOD;

int mult_a[7005];
int mult_b[7005];
int mult_x[7005];
int mult_y[7005];

inline pair<int, int> f(const pair<int, int> &p) {
    int answer = mult_a[p.first] + mult_b[p.second] + mult_x[p.first] + mult_y[p.second] + z;
    while (answer >= MOD) {
        answer -= MOD;
    }
    return make_pair(p.second, answer);
}

pair<int, int> detect(const pair<int, int> &x0) {
    pair<int, int> tortoise, hare;
    tortoise = f(x0);
    hare = f(tortoise);
    while (hare != tortoise) {
        hare = f(f(hare));
        tortoise = f(tortoise);
    }
    int length = 0;
    tortoise = x0;
    while (tortoise != hare) {
        length += 1;
        tortoise = f(tortoise);
        hare = f(hare);
    }
    int cycle = 1;
    hare = f(tortoise);
    while (hare != tortoise) {
        hare = f(hare);
        cycle += 1;
    }
    return make_pair(length, cycle);
}

int main() {
    ifstream fin("rsir.in");
    ofstream fout("rsir.out");
    long long n;
    fin >> t0 >> t1 >> a >> b >> x >> y >> z >> MOD >> n;
    for (int i = 0; i < MOD; ++ i) {
        mult_a[i] = 1LL * i * i * a % MOD;
        mult_b[i] = 1LL * i * i * b % MOD;
        mult_x[i] = i * x % MOD;
        mult_y[i] = i * y % MOD;
    }
    t0 = t0 % MOD; t1 = t1 % MOD;
    pair<int, int> cycle = detect(make_pair(t0, t1));
    pair<int, int> p(t0, t1);
    for (int i = 1; i <= min(n, 1LL * cycle.first); ++ i) {
        p = f(p);
    }
    if (n <= cycle.first) {
        fout << p.first << "\n";
    }
    n -= cycle.first;
    n %= cycle.second;
    for (int i = 1; i <= n; ++ i) {
        p = f(p);
    }

    fout << p.first << "\n";
    return 0;
}