Cod sursa(job #735632)

Utilizator HulkIncredibilul Hulk Hulk Data 16 aprilie 2012 21:48:19
Problema Rsir Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<stdio.h>
#include<set>
using namespace std;

#define pi pair<int,int>
#define x first
#define y second
#define mp make_pair
#define ll long long

ll n;
int t0,t1,a,b,x,y,z,MOD,ind1,ind2;
int prep[2][7005],val;
pi val1,val2;

inline int calc(int v1,int v2)
{
	val = prep[0][v1] + prep[1][v2];	
	if(val >= MOD)
		val -= MOD;
	return val;	
}

inline pi Next(pi val)
{
	return mp(val.y, calc(val.x,val.y));
}

int main ()
{
	int i;
	
	freopen("rsir.in","r",stdin);
	freopen("rsir.out","w",stdout);
	
	scanf("%d%d%d%d%d%d%d%d%lld",&t0,&t1,&a,&b,&x,&y,&z,&MOD,&n);
	if(!n)
	{
		printf("%d\n",t0);
		return 0;
	}
	if(n == 1)
	{
		printf("%d\n",t1);
		return 0;
	}
	for(i = 0; i < MOD; i++)
	{
		prep[0][i] = (((i * i) % MOD) * a + i * x + z) % MOD; 
		prep[1][i] = (((i * i) % MOD) * b + i * y) % MOD; 
	}	
	
	ind1 = ind2 = 1;
	val1 = mp(t0 % MOD,t1 % MOD);	
	val2 = mp(t0 % MOD,t1 % MOD);
			
	for(; ;)
	{
		ind1++;
		val1 = Next(val1);
		ind2 += 2;
		val2 = Next(Next(val2));
		if(ind1 == n)
		{
			printf("%d\n",val1.y);
			return 0;
		}
		if(val1 == val2)
			break;
	}		
	i = ind2 - ind1;
	n = (n - ind1) % i;
	for(val2 = val1; n; n--, val2 = Next(val2));
	
	printf("%d\n",val2.y);
	
	return 0;
}