首页 > 代码库 > hdu 4549 M斐波那契数列 矩阵快速幂+欧拉定理
hdu 4549 M斐波那契数列 矩阵快速幂+欧拉定理
M斐波那契数列
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Problem Description
M斐波那契数列F[n]是一种整数数列，它的定义如下：
F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )
现在给出a, b, n，你能求出F[n]的值吗？
F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )
现在给出a, b, n，你能求出F[n]的值吗？
Input
输入包含多组测试数据；
每组数据占一行，包含3个整数a, b, n（ 0 <= a, b, n <= 10^9 ）
每组数据占一行，包含3个整数a, b, n（ 0 <= a, b, n <= 10^9 ）
Output
对每组测试数据请输出一个整数F[n]，由于F[n]可能很大，你只需输出F[n]对1000000007取模后的值即可，每组数据输出一行。
Sample Input
0 1 06 10 2
Sample Output
060
Source
2013金山西山居创意游戏程序挑战赛——初赛（2）
思路：原始的斐波那契是F(n)=x*f(1)+y*f(2);
然后同样的本题的F(n)=f(1)^x*f(2)^y;
根据费马小定理，或者欧拉定理，对于指数进行x(y)%(mod-1);
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cmath>#include<string>#include<queue>#include<algorithm>#include<stack>#include<cstring>#include<vector>#include<list>#include<set>#include<map>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14#define bug(x) cout<<"bug"<<x<<endl;const int N=2e5+10,M=1e6+10,inf=1e9+7;const ll INF=1e18+10,mod=1e9+7;ll MOD;struct Matrix{ ll a[2][2]; Matrix() { memset(a,0,sizeof(a)); } void init() { for(int i=0;i<2;i++) for(int j=0;j<2;j++) a[i][j]=(i==j); } Matrix operator + (const Matrix &B)const { Matrix C; for(int i=0;i<2;i++) for(int j=0;j<2;j++) C.a[i][j]=(a[i][j]+B.a[i][j])%MOD; return C; } Matrix operator * (const Matrix &B)const { Matrix C; for(int i=0;i<2;i++) for(int k=0;k<2;k++) for(int j=0;j<2;j++) C.a[i][j]=(C.a[i][j]+1LL*a[i][k]*B.a[k][j])%MOD; return C; } Matrix operator ^ (const ll &t)const { Matrix A=(*this),res; res.init(); ll p=t; while(p) { if(p&1)res=res*A; A=A*A; p>>=1; } return res; }};ll quickmod(ll a,ll b,ll c){ ll ans=1; while(b) { if(b&1)ans=(ans*a)%c; b>>=1; a=(a*a)%c; } return ans;}int main(){ ll a,b,n; Matrix base,ans; base.a[0][0]=1;base.a[0][1]=1; base.a[1][0]=1;base.a[1][1]=0; MOD=1e9+6; while(~scanf("%lld%lld%lld",&a,&b,&n)) { if(n==0) printf("%lld\n",a); else if(n==1) printf("%lld\n",b); else { ans=base^(n-1); ll x=quickmod(b,ans.a[0][0],1e9+7); ll y=quickmod(a,ans.a[0][1],1e9+7); printf("%lld\n",(x*y)%mod); } } return 0;}
hdu 4549 M斐波那契数列 矩阵快速幂+欧拉定理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。