https://vj.xtuacm.cf/contest/view.action?cid=115#status//-/0/ 求F(a^b)^(F(a^b)^(n-1))%c a,b,n是longlong范围内的正整数 c是一个小于300的余数
思路： 不难发现c小于300是有意而为的 这里有两个定理： 1.在模c的状态下，斐波那契具有循环节性质，即F[a^b]=F[a^b%len] len即循环节 2.我们可以通过欧拉函数来进行降幂，即a^b%c=a^(b%φ(c)+φ(c))%c
F(a^b)^(F(a^b)^(n-1))%c
= F(a^b)^(F(a^b)^(n-1)%φ(c)+φ(c))%c
=F(a^b%loop1)^(F(a^b%loop2)^(n-1)%φ(c)+φ(c))%c
–》先将斐波那契循环节找到（loop1表示模c状态下的循环节，loop2表示模φ(c)状态下的循环节）
这样就可以直接用快速幂求了
分析：原式等价于求
有一点没明白的就是大多数题解的方案都是特判c=1与φ(c)=1的情况 ，发现特美特判其实都一样c=1的时候就是0 φ(c)=1的时候c=1或c=2，可以直接输出a
/* 设t=a^b;G(1)=F[t]; 根据递推公式G(n)=G(n-1)^F[t];可知：G(2)=F[t]^F[t];G(3)=(F[t]^F[t])^F[t]=F[t]^(F[t]*F[t]); 这样我们能看出G(n)=F[t]^(F[t]^(n-1)); 首先我们在这里要先解决F[t]的值，由于a，b的值都比较大，所以求a^b是不现实的（java你可以试试） 但是我们取余的C是比较小的，所以可以使用循环节来求出F[t]%C的值，设A=F[t]%C; 接下来求A^(F[t]^(n-1))%C的值，这里还是由于F[t]的值是没有办法求的，所以需要用到取余来简化计算， 那么我们会想到费马小定理，欧拉公式，但是这里没说C是素数，所以要用到万能公式来求解， 即首先要求出φ(C),然后再求出循环节，得到F[t]%φ(C)的值，这样我们就能求解了。 注意C=1和欧拉函数值为1的情况。 */ #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #define ll unsigned long long ll f[5500]; using namespace std; int sch(int c) { int loop; f[0]=0,f[1]=1; for(int i=2; i<2005; i++) { f[i]=(f[i-1]%c+f[i-2]%c)%c; if(f[i-1]==0&&f[i]==1) { loop=i; break; } } return loop-1; } int phi(int n) { int rea=n; for(int i=2; i*i<=n; i++) { if(n%i==0) { rea=rea-rea/i; while(n%i==0) n=n/i; } } if(n>1) rea=rea-rea/n; return rea; } ll multi(ll a,ll b,ll mod) { ll ans=0; while(b) { if(b&1) ans=(ans+a)%mod; b>>=1; a=(a+a)%mod; } return ans; } ll quick_pow(ll m,ll n,ll mod) { ll ans=1; m=m%mod; while(n) { if(n&1)ans=multi(ans,m,mod); n>>=1; m=multi(m,m,mod); } return ans; } int main() { int t,c; ll a,b,n; scanf("%d",&t); int tt=1; while(t--) { scanf("%I64u %I64u %I64u %d",&a,&b,&n,&c); if(c==1) { printf("Case %d: 0\n",tt++); continue; } int p=phi(c); int loop1=sch(c); ll t1=quick_pow(a,b,loop1); ll tmp1=f[t1]%c; int loop2=sch(p); ll t2=quick_pow(a,b,loop2); ll tmp2=f[t2]%p; tmp2=quick_pow(tmp2,n-1,p); tmp2+=p; tmp1=quick_pow(tmp1,tmp2,c); printf("Case %d: %I64u\n",tt++,tmp1); } return 0; }