首页 > 代码库 > hdu 4549 M斐波那契数列

hdu 4549 M斐波那契数列

2024-08-03 05:46:30   221人阅读

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 }
View Code

 

hdu 4549 M斐波那契数列


联系
我们