P1306 斐波那契公约数（ksm+结论）-白红宇

P1306 斐波那契公约数（ksm+结论）

阅读量：5010 次

发布时间：2019-06-12

本文共 1217 字，大约阅读时间需要 4 分钟。

题目描述

对于Fibonacci数列：1,1,2,3,5,8,13......大家应该很熟悉吧~~~但是现在有一个很“简单”问题：第n项和第m项的最大公约数是多少？

Update：加入了一组数据。

输入输出格式

输入格式：

两个正整数n和m。（n,m<=10^9）

注意：数据很大

输出格式：

Fn和Fm的最大公约数。

由于看了大数字就头晕，所以只要输出最后的8位数字就可以了。

输入输出样例

输入样例#1：

4 7

输出样例#1：

1 结论：gcd(F[n],F[m])=F[gcd(n,m)] 就是一个ksm了 代码：

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #define mod 100000000const int maxn=1e5+5;typedef long long ll;using namespace std;struct mat{ ll a[5][5]; };mat mul(mat x,mat y){ mat ans; memset(ans.a,0,sizeof(ans.a)); for(int i=0;i<2;i++) { for(int j=0;j<2;j++) { for(int k=0;k<2;k++) { ans.a[i][j]=(ans.a[i][j]+x.a[i][k]*y.a[k][j])%mod; } } } return ans;}mat ans;ll ksm(int x){ mat res; res.a[0][0]=1; res.a[0][1]=1; res.a[1][0]=1; res.a[1][1]=0; while(x) { if(x&1) { ans=mul(ans,res); } x>>=1; res=mul(res,res); } return ans.a[0][0]%mod;}int main(){ int n,m; cin>>n>>m; int x=__gcd(n,m); memset(ans.a,0,sizeof(ans.a)); ans.a[0][0]=1; ans.a[1][0]=1; ll answer=ksm(x-1); printf("%lld\n",answer); return 0;}