【雅礼联考DAY01】数列

#include<cstdio>
#include<map>
using namespace std;
typedef long long LL;

const int N = 1e6;
LL x , a , b , c , m , f[N + 10] , p;
int n , len , vis[N + 10];

inline LL fpow(LL x , int y , LL p)
{
	LL res = 1;
	while (y)
	{
		if (y & 1) res = res * x % p;
		x = x * x % p , y = y >> 1;
	}
	return res;
}

int main()
{
//	freopen("数列.in" , "r" , stdin);
	scanf("%lld%lld%lld%lld%d%lld" , &x , &a , &b , &c , &n , &m);
	x %= m;
	if (n < 1000000)
	{
		for(register int i = 1; i <= n; i++) x = (a * x % m * x % m + b * x % m + c) % m;
		printf("%lld" , x);
		return 0;
	}
	if (m <= 1000000) 
	for(register int i = 1; i <= m + 5; i++)
	{
		x = (a * x % m * x % m + b * x % m + c) % m;
		f[i] = x;
		if (i == n)
		{
			printf("%lld" , x);
			return 0;
		}
		if (vis[x])
		{
			len = i - vis[x] , n = (n - i) % len;
			printf("%lld" , f[vis[x] + n]);
			return 0;
		}
		else vis[x] = i;
	}
	c = b / (a << 1);
	p = fpow(x + c , fpow(2LL , n , m - 1) , m);
	a = fpow(a , fpow(2LL , n , m - 1) - 1 , m);
	x = (p * a % m + m - c) % m; 
	printf("%lld" , x);
}
/*
b = 2ak
4ac = b*b - 2b
4ac = 4*a*a*k*k-4*a*k
c = a*k*k-k
f(x) = a*x*x+b*x+c
f(x) = a*x*x+2*x*a*k+a*k*k-k
f(x) = a(x+k)^2-k
p = x+k
p(i) = a*p(i-1)^2
p(0) = x(0)+k
p(1) = a*p(0)^2
p(2) = a*a*a*p(0)^4
p(3) = a^7*p(1)^8
p(n) = a^(2^n-1)*p(0)^(2^n)
ans = p(n)-k;
a^(m-1) % m = 1 (a,m) = 1
*/