一道找循环节的题，RE了很多发。
要用到一个转换式子：a^b%c=[(a%c)^(b%phi(c)+phi(c))]%c
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> #define ull unsigned long long using namespace std; int f[222222]; int findloop(int c) { f[0]=0,f[1]=1; for(int i=2;;++i) { f[i]=(f[i-1]+f[i-2])%c; if(f[i]==1&&0==f[i-1]) return i-1; } } int phi(int n) { int m=(int)sqrt(n+0.5); int ans=n; for(int i=2;i<=m;++i) if(n%i==0) { ans=ans/i*(i-1); while(n%i==0) n/=i; } if(n>1) ans=ans/n*(n-1); return ans; } int q_mod(ull a,ull b,int md) { a%=md; int ans=1; while(b) { if(b&1) { ans=ans*a%md; } b>>=1; a=a*a%md; } return ans; } int main() { int kas=1; int _; scanf("%d",&_); ull a,b,n; int c,loop1,loop2,phic; int d,z,ans; while(_--) { scanf("%I64u%I64u%I64u%d",&a,&b,&n,&c); printf("Case %d: ",kas); ++kas; if(c==1) { //第一个要注意的地方 puts("0"); continue; } loop1=findloop(c); d=q_mod(a,b,loop1); d=f[d]%c; phic=phi(c); if(phic==1) z=phic; //第二个要注意的地方，不然会疯狂RE else { loop2=findloop(phic); z=q_mod(a,b,loop2); z=q_mod(f[z],n-1,phic); z+=phic; } ans=q_mod(d,z,c); cout<<ans<<endl; } }