Cod sursa(job #1227196)

Utilizator assa98Andrei Stanciu assa98 Data 9 septembrie 2014 17:31:58
Problema Rsir Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <iostream>
#include <algorithm>

#define pe pair<int, int>
#define fi first
#define se second
#define mp make_pair

using namespace std;

ifstream fin("rsir.in");
ofstream fout("rsir.out");

const int MAX_M = 7010;

int ra[MAX_M];
int rb[MAX_M];

int M, z;

pe get(pe t) {
    int x = ra[t.fi] + rb[t.se];
    if(x > M) {
        x -= M;
    }
    x += z;
    if(x > M) {
        x -= M;
    }
    
    return mp(t.se, x);
}

int main() {
    int T0, T1, a, b, x, y;
    long long n;
    
    fin >> T0 >> T1 >> a >> b >> x >> y >> z >> M >> n;
    
    T0 %= M;
    T1 %= M;

    if(n == 0) {
        fout << T0;
        return 0;
    }

    if(n == 1) {
        fout << T1;
        return 0;
    }
    
    if(M == 1) {
        fout << 0;
        return 0;
    }

    for(int i = 0; i <= M; i++) {
        ra[i] = ((long long)a * i * i + x * i) % M;
        rb[i] = ((long long) b * i * i + y * i) % M;
    }

    pe p1 = mp(T0, T1);
    pe p2 = p1;

    int c1 = 2, c2 = 3;

    p1 = get(p1);
    p2 = get(get(p2));
    while(p1 != p2) {
        if(c1 == n) {
            fout << p1.se;
            return 0;
        }
        
        p1 = get(p1);
        c1++;

        //cout << p1.se << ' ';
        p2 = get(get(p2));
        c2 += 2;
    }

    int l;
    for(p2 = get(p2), l = 1; p2 != p1; p2 = get(p2), l++);
    
    n %= l;


    for(p1 = mp(T0, T1); n; p1 = get(p1), n--);
    fout << p1.fi;
    return 0;
}