Colossal Fibonacci Numbers!（裴波那切数列性质）

本文主要是介绍Colossal Fibonacci Numbers!（裴波那切数列性质），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：就是让你求f(a^b)%n。数据大，很明显暴力是不可能的，这辈子都不可能的…

思路：裴波那切数列有一个性质，尾数循环。

斐波那契数列的个位数：一个60步的循环

最后两位数是一个300步的循环

最后三位数是一个1500步的循环

最后四位数是一个15000步的循环

最后五位数是一个150000步的循环

求出对应的循环周期，问题就变成了快速幂取模了。

#include<stdio.h>
#include<string.h>
typedef unsigned long long ull;
ull f[1000100];
ull quick_mod(ull a,ull b,ull n)
{ull res=1;while(b){if(b&1)res=((res%n)*(a%n))%n;a=((a%n)*(a%n))%n;   //由于给出的n比较大所以~b>>=1;     //>>和<<符号省时}return res%n;
}
int main()
{int t,i,j;ull a,b,n,s,q;scanf("%d",&t);while(t--){scanf("%llu%llu%llu",&a,&b,&n);  //数据大，用llu存if(a==0||n==1){printf("0\n");continue;}int ans=0;f[0]=0,f[1]=1;f[2]=1;for(i=2; i<=n*n; i++) //裴波那切数列一性质：不超过n*n{f[i]=(f[i-1]+f[i-2])%n;ans++;          //循环周期if(f[i]==1&&f[i-1]==0)break;}int p=quick_mod(a,b,ans);printf("%llu\n",f[p]);}return 0;
}

这篇关于Colossal Fibonacci Numbers!（裴波那切数列性质）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---