Cod sursa(job #68542)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 28 iunie 2007 12:39:47
Problema Rsir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define MAXMOD 7005

long long N;
int T0, T1, a, b, x, y, z, MOD;

		//precalca[i] = (i * i * a) % MOD
		//precalcb[i] = (i * i * b) % MOD
short precalca[MAXMOD], precalcb[MAXMOD];
		//precalcx[i] = (i * x) % MOD
		//precalcy[i] = (i * y) % MOD
short precalcx[MAXMOD], precalcy[MAXMOD];

inline pair<int, int> getNew( const pair<int, int> &prv )
{
	int rez = precalca[ prv.first ] + precalcb[ prv.second ];
	if (rez >= MOD)
		rez -= MOD;
	rez += precalcx[ prv.first ];
	if (rez >= MOD)
		rez -= MOD;
	rez += precalcy[ prv.second ];
	if (rez >= MOD)
		rez -= MOD;
	rez += z;
	if (rez >= MOD)
		rez -= MOD;
	return make_pair( prv.second, rez );
}

int main()
{
	freopen("rsir.in", "rt", stdin);
	freopen("rsir.out", "wt", stdout);
	scanf("%d %d %d %d %d %d %d %d %lld", &T0, &T1, &a, &b, &x, &y, &z, &MOD, &N);

	T0 %= MOD; T1 %= MOD;
	a %= MOD; b %= MOD; x %= MOD; y %= MOD; z %= MOD;

	if (N == 0)
	{
		printf("%d\n", T0);
		return 0;
	}
	if (N == 1)
	{
		printf("%d\n", T1);
		return 0;
	}

	for (int i = 0; i < MOD; i++)
	{
		int aux = (i * i) % MOD;
		precalca[i] = (aux * a) % MOD;
		precalcb[i] = (aux * b) % MOD;
		precalcx[i] = (i * x) % MOD;
		precalcy[i] = (i * y) % MOD;
	}

	pair<int, int> cur = make_pair(T0, T1), nxt, goal;
	for (int i = 2; i <= MOD * MOD + 1; cur = nxt, i++)
		nxt = getNew(cur);
	goal = cur;

	cur = make_pair(T0, T1);
	for (int i = 1; i <= MOD * MOD + 1; cur = nxt, i++)
	{
		if (i == N)
		{
			printf("%d\n", cur.second);
			return 0;
		}
		
		if (cur == goal)
		{
			int start = i, len = MOD * MOD - i + 1;

			N -= start; N %= len;

			for (int k = 1; k <= N; cur = nxt, k++)
				nxt = getNew(cur);

			printf("%d\n", cur.second);
			return 0;
		}
		nxt = getNew(cur);
	}
		
	return 0;
}