一看就是欧拉降幂，问题是怎么求$fib(a^b)$，C给的那么小显然还是要找循环节。数据范围出的很那啥..unsigned long long注意用防爆的乘法
/** @Date : 2017-09-25 15:17:05
* @FileName: HDU 2814 斐波那契循环节 欧拉降幂.cpp
* @Platform: Windows
* @Author : Lweleth (SoungEarlf@gmail.com)
* @Link : https://github.com/
* @Version : $Id$
*/
#include <bits/stdc++.h>
#define LL unsigned long long
#define PII pair<int ,int>
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std;
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
LL mul(LL a, LL b, LL m) {
LL ans = 0;
while (b) {
if (b & 1) {
ans = (ans + a) % m;
b--;
}
b >>= 1;
a = (a + a) % m;
}
return ans;
}
/* RERERERERE 精度
LL mul(LL x, LL y, LL mod)
{
return (x * y - (LL)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}*/
/*
struct Matrix
{
LL m[M][M];
};
Matrix A;
Matrix I = {1, 0, 0, 1};
Matrix multi(Matrix a, Matrix b, LL MOD)
{
Matrix c;
for(int i = 0; i < M; i++)
{
for(int j = 0; j < M; j++)
{
c.m[i][j] = 0;
for(int k = 0; k < M; k++)
c.m[i][j] = (c.m[i][j] % MOD + (a.m[i][k] % MOD) * (b.m[k][j] % MOD) % MOD) % MOD;
c.m[i][j] %= MOD;
}
}
return c;
}
Matrix power(Matrix a, LL k, LL MOD)
{
Matrix ans = I, p = a;
while(k)
{
if(k & 1)
{
ans = multi(ans, p, MOD);
k--;
}
k >>= 1;
p = multi(p, p, MOD);
}
return ans;
}
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
const int N = 400005;
const int NN = 5005;
LL num[NN], pri[NN];
LL fac[NN];
int cnt, c;
bool prime[N];
int p[N];
int k;
void isprime()
{
k = 0;
memset(prime, true, sizeof(prime));
for(int i = 2; i < N; i++)
{
if(prime[i])
{
p[k++] = i;
for(int j = i + i; j < N; j += i)
prime[j] = false;
}
}
}
LL fpow(LL a, LL b, LL m)
{
LL ans = 1;
a %= m;
while(b)
{
if(b & 1)
{
ans = mul(ans, a , m);
b--;
}
b >>= 1;
a = mul(a , a , m);
}
return ans;
}
LL legendre(LL a, LL p)
{
if(fpow(a, (p - 1) >> 1, p) == 1)
return 1;
else return -1;
}
void Solve(LL n, LL pri[], LL num[])
{
cnt = 0;
LL t = (LL)sqrt(1.0 * n);
for(int i = 0; p[i] <= t; i++)
{
if(n % p[i] == 0)
{
int a = 0;
pri[cnt] = p[i];
while(n % p[i] == 0)
{
a++;
n /= p[i];
}
num[cnt] = a;
cnt++;
}
}
if(n > 1)
{
pri[cnt] = n;
num[cnt] = 1;
cnt++;
}
}
void Work(LL n)
{
c = 0;
LL t = (LL)sqrt(1.0 * n);
for(int i = 1; i <= t; i++)
{
if(n % i == 0)
{
if(i * i == n) fac[c++] = i;
else
{
fac[c++] = i;
fac[c++] = n / i;
}
}
}
}
LL get_loop(LL n)
{
Solve(n, pri, num);
LL ans = 1;
for(int i = 0; i < cnt; i++)
{
LL record = 1;
if(pri[i] == 2)
record = 3;
else if(pri[i] == 3)
record = 8;
else if(pri[i] == 5)
record = 20;
else
{
if(legendre(5, pri[i]) == 1)
Work(pri[i] - 1);
else
Work(2 * (pri[i] + 1));
sort(fac, fac + c);
for(int k = 0; k < c; k++)
{
Matrix a = power(A, fac[k] - 1, pri[i]);
LL x = (a.m[0][0] % pri[i] + a.m[0][1] % pri[i]) % pri[i];
LL y = (a.m[1][0] % pri[i] + a.m[1][1] % pri[i]) % pri[i];
if(x == 1 && y == 0)
{
record = fac[k];
break;
}
}
}
for(int k = 1; k < num[i]; k++)
record *= pri[i];
ans = ans / gcd(ans, record) * record;
}
return ans;
}
LL fib[5005];
void Init()
{
A.m[0][0] = 1;
A.m[0][1] = 1;
A.m[1][0] = 1;
A.m[1][1] = 0;
fib[0] = 0;
fib[1] = 1;
for(int i = 2; i < 5005; i++)
fib[i] = fib[i - 1] + fib[i - 2];
}*///会爆ULL C比较小300 不如直接求
LL fib[5500];
LL get_loop(LL n)
{
LL lp = -1;
fib[0] = 0, fib[1] = 1;
for(int i = 2; i < 2010; i++)
{
fib[i] = (fib[i - 1] % n + fib[i - 2] % n) % n;
if(fib[i] == 1 && fib[i - 1] == 0)
return lp = i - 1;
}
return lp;
}
LL fpow(LL a, LL n, LL mod)
{
LL res = 1;
a %= mod;
while(n)
{
if(n & 1)
res = mul(res, a, mod);
a = mul(a, a, mod);
n >>= 1;
}
return res;
}
int get_phi(int x)
{
int ans = x;
for (int i = 2; i * i <= x; i++)
{
if (x % i == 0)
{
while (x % i == 0)
x /= i;
ans = ans - ans / i;
}
}
if (x > 1)
ans = ans - ans / x;
return ans;
}
int main()
{
LL n;
//Init();
//isprime();
int T;
cin >> T;
int icas = 0;
while(T--)
{
LL a, b, n, C;
scanf("%llu%llu%llu%llu", &a, &b, &n, &C);
if(C == 1)
{
printf("Case %d: 0
", ++icas);
continue;
}
int lp1 = get_loop(C);
LL e1 = fpow(a, b, lp1);
LL ans1 = fib[e1] % C;
LL phi = get_phi(C);
int lp2 = get_loop(phi);
LL e2 = fpow(a, b, lp2);
LL ans2 = fpow(fib[e2] % phi, n - 1, phi) + phi;
LL ans = fpow(ans1, ans2, C);
printf("Case %d: %llu
", ++icas, ans);
}
return 0;
}