【雅礼联考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

*/
巴特西

【雅礼联考DAY01】数列

最新文章

热门文章
