Cod sursa(job #271845)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 5 martie 2009 23:43:42
Problema Rsir Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
using namespace std;

#include <vector>
#include <bitset>
#define f first
#define s second
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define CC(v) memset((v),0,sizeof((v)))
#define CP(v,w) memcpy((v),(w),sizeof((w)))
#define mp make_pair
#define IN  "rsir.in"
#define OUT "rsir.out"
#define M_MAX 1<<13

//Tn = a * Tn-2^2 + b * Tn-1^2 + x * Tn-2 + y * Tn-1 + z

typedef pair<int,int> pi;
int T0,T1,a,b,x,y,z,M;
int S1[1<<13],S2[1<<13];
ll N;

void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	scanf("%d%d%d%d%d%d%d%lld%d",&T0,&T1,&a,&b,&x,&y,&z,&M,&N);
	z %= M;
}

void next(pi &m)
{
	int nm = S1[m.f] + S2[m.s] + z;
	for(;nm >= M;nm -= M);
	m.f = m.s;
	m.s = nm;
}

void solve()
{
	int per(1),nper(0);
	pi m1,m2;
	FOR(i,0,M-1)
		S1[i] = (a * i * i + x * i) % M,
		S2[i] = (b * i * i + y * i) % M;

	next(m1 = mp(T0,T1));
	next(m2 = m1);;
	for(;m1 != m2;next(m1),next(m2),next(m2) );
	for(m2 = mp(T0,T1);m2 != m1;next(m2),++nper);
	for(next(m2=m1);m1 != m2;next(m2),++per);
	
	if(N <= (ll)nper)
	{
		m2 = mp(T0,T1);
		FOR(i,1,N) next(m2);
		printf("%d\n",m2.f);
		return;
	}
	N -= nper;
	N -= (N / per) * (ll)per;
	
	m2 = m1;
	FOR(i,1,N) next(m2);
	printf("%d\n",m2.f);
}

int main()
{
	scan();
	solve();
	return 0;
}