首页 > 代码库 > [快速幂][UVa11582]巨大的斐波那契数列!
[快速幂][UVa11582]巨大的斐波那契数列!
题目大意
输入a, b, n, 计算f( a ^ b) % n ， f( i ) = f( i - 1) + f( i - 2 ) ， f( 0 ) = f(1) = 1, 其中，0 <= a , b <= 2 ^ 64, 0 <= n <= 1000
思考
首先扔出两个结论（证明过程链接在此，个人水平有限看不懂。）
1.斐波那契数列模n 必有循环节。
2.斐波那契数列模n 的情况下，最多n^2项就会出现重复。
先找出循环节M，之后计算a^b%M 是多少，输出fib[a^b%M]即可
代码实现
#include<queue>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>typedef unsigned long long ll;using namespace std;const int maxn=1000+10;ll a,b;int f[maxn*maxn],n,M;int pow(ll a,ll p,int Mod){ int ret=1; while(p) { if(p & 1)ret*=a,ret%=Mod; a*=a;a%=Mod; p>>=1; } return ret;}inline void solve(){ cin>>a>>b>>n; if(n==1||!a){printf("0\n");return ;} f[1]=1,f[2]=1; for(int i=3;i<=n*n+10;i++) { f[i]=f[i-1]+f[i-2];f[i]%=n; if(f[i]==f[2]&&f[i-1]==f[1]) {M=i-2;break;} } int k=pow(a%M,b,M); printf("%d\n",f[k]);}int main(){ int T;cin>>T; while(T--) solve(); return 0;}
[快速幂][UVa11582]巨大的斐波那契数列!
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。