首页 > 代码库 > hdu 4549 M斐波那契数列
hdu 4549 M斐波那契数列
http://acm.hdu.edu.cn/showproblem.php?pid=4549
思路：
观察a,b的幂符合斐波那契数列，因为n特别的大，所以构造矩阵求出a,b的第n的幂。 构造矩阵之后矩阵快速幂,因为在快速幂的时候矩阵相乘会超出__int64。所以需要用到一个定理
当gcd(a,mod)==1的时候
a^x = a^( x mod Eular(mod) ) ( mod mod ) . 所以变成这样a^b%mod=a^(b%(mod-1))%mod;
1 #include <cstdio> 2 #include<cstring> 3 #include <algorithm> 4 #define LL __int64 5 using namespace std; 6 const int mod=1e9+7; 7 8 LL a,b,n; 9 10 struct node11 {12 LL a[4][4];13 };14 15 node mul(node x,node y)16 {17 node c;18 for(int i=0; i<2; i++)19 {20 for(int j=0; j<2; j++)21 {22 c.a[i][j]=0;23 for(int k=0; k<2; k++)24 {25 c.a[i][j]+=x.a[i][k]*y.a[k][j];26 c.a[i][j]%=(mod-1);27 }28 }29 }30 return c;31 }32 33 node pow_m(node c,int n)34 {35 node temp;36 memset(temp.a,0,sizeof(temp.a));37 temp.a[0][0]=1; temp.a[1][1]=1;38 node xx=c;39 while(n)40 {41 if(n&1) temp=mul(temp,xx);42 xx=mul(xx,xx);43 n>>=1;44 }45 return temp;46 }47 48 LL pow_M(LL a,LL n)49 {50 LL ans=1;51 LL temp=a%mod;52 while(n)53 {54 if(n&1)55 {56 ans*=temp;57 ans%=mod;58 }59 temp*=temp;60 temp%=mod;61 n>>=1;62 }63 return ans;64 }65 66 int main()67 {68 node tem;69 tem.a[0][0]=0; tem.a[0][1]=1;70 tem.a[1][0]=tem.a[1][1]=1;71 while(scanf("%I64d%I64d%I64d",&a,&b,&n)!=EOF)72 {73 node st=pow_m(tem,n);74 printf("%I64d\n",(pow_M(a,st.a[0][0])*pow_M(b,st.a[1][0]))%mod);75 }76 return 0;77 }
hdu 4549 M斐波那契数列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。