Cod sursa(job #526001)

Utilizator AndreyPAndrei Poenaru AndreyP Data 26 ianuarie 2011 22:50:55
Problema Rsir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pii pair< int,int >
#define ll long long

int t0,t1,a,b,x,y,z;
int M;
ll n;
ll L1,L2;
int pre1[7010],pre2[7010];

inline void getNext(pii &p) {
	//int aux = (a*((p.fs*p.fs)%M) + b*((p.sc*p.sc)%M) + x*p.fs + y*p.sc + z) % M;     

	int aux = pre1[p.fs] + pre2[p.sc];
	if(aux>=M)
		aux -= M;

        p.fs = p.sc;
	p.sc = aux;
}

inline void precalc() {
	int aux;
	for(int i=0; i<M; ++i) {
		aux = (i*i)%M;
		pre1[i] = (a*aux + x*i) % M;
		pre2[i] = (b*aux + y*i + z) % M;
	}
}

int main() {
	freopen("rsir.in","r",stdin);
	freopen("rsir.out","w",stdout);
	
	pii iep,tes;
	scanf("%d%d%d%d%d%d%d%d%lld",&iep.fs,&iep.sc,&a,&b,&x,&y,&z,&M,&n);
	if(n==0) {
		printf("%d\n",iep.fs);
		return 0;
	}
	if(n==1) {
		printf("%d\n",iep.sc);
		return 0;
	}

	precalc();

        tes = iep;
	t0 = iep.fs;
	t1 = iep.sc;

	do {
		getNext(tes);
		getNext(iep);
		getNext(iep);
	} while(tes!=iep);

        do {
		getNext(iep);
		++L2;
	}while(tes!=iep);

	iep = mp(t0,t1);

	while(tes!=iep) {
		getNext(iep);
		getNext(tes);
		++L1;
	}

	if(n<=L1) {
		iep = mp(t0,t1);
		for(int i=1,n1=(int)n; i<n1; ++i)
			getNext(iep);
		printf("%d\n",iep.fs);
		return 0;
	}

	n -= L1;
	n %= L2;
	for(int i=0,n1=(int)n; i<n1; ++i)
		getNext(iep);
	printf("%d\n",iep.fs);

	return 0;
}