通过打表可以发现 斐波那契数列模除某个数的结果会呈现一定的周期性 数列中的某个数取决于前两个数，当某个数与下一个数的模除结果与 f0 f1相同 ，即开始了一个新的周期; 取决于前两个数 每一个数模除n有n种可能，两个数是n×n，即循环节中的元素不会超过n×n; 先打表将n为1～1000的每个周期数打出来，a^b%（每个i对应的周期数），利用快速幂模除，模除结果<=n，直接求得即可 #include #include using namespace std; const int maxn=1e6+10; int q[maxn]; int ss[maxn]; int sto[1010]; typedef unsigned long long ll; void ser() { sto[1]=1; for (int j=2;j<=1000;j++) { q[0]=0%j;q[1]=1%j; for (int i=2;i<=j*j;i++) { q[i]=(q[i-1]%j+q[i-2]%j)%j; if (q[i]==1&&q[i-1]==0) { sto[j]=i-1; break; } } } } ll mi(ll a,ll b,ll c) { ll ans=1; a=a%c; while (b!=0) { if (b&1) ans=(ans*a)%c; b>>=1; a=(a*a)%c; } return ans; } int main() { int t; ll a,b,c; ser(); cin>>t; while (t--) { scanf("%llu%llu%llu",&a,&b,&c);//unsigned long long 的输入 int len=sto[c]; ll cnt=mi(a,b,len); ss[0]=0%c;ss[1]=1%c; for (int i=2;i<=cnt;i++) ss[i]=(ss[i-1]+ss[i-2])%c; if (a==0&&b==0) printf("0 "); else printf("%d ",ss[cnt]); } return 0; }