对于Fibonacci数列：1,1,2,3,5,8,13......大家应该很熟悉吧~~~但是现在有一个很“简单”问题：第n项和第m项的最大公约数是多少？
输入格式：
两个正整数n和m。（n,m<=10^9）
注意：数据很大
输出格式：
Fn和Fm的最大公约数。
由于看了大数字就头晕，所以只要输出最后的8位数字就可以了。
用递归&递推会超时
用通项公式也会超时
题解：
这道题自己实在想不出来，看的题解，看到了那个可爱的性质gcd(f[n],f[m])=f[gcd(n,m)] （f数组表示斐波那契数列）
超级可爱有木有！
于是我就想它是怎么证出来的
参考网上各方题解加上自己的总结理解 证明过程如下：
先可证引理一：gcd(f[n],f[n+1])=1
由辗转相除 gcd(f[n],f[n+1]) = gcd(f[n],f[n+1]-f[n]) = gcd(f[n],f[n-1]) = gcd(f[n-1],f[n-2]) = …= gcd(f[2],f[1]) = 1
引理二：f[m+n]=f[m] * f[n-1] + f[m-1] * f[n]
可直接根据斐波那契数列性质（f[n]=f[n-1]+f[n-2]）推
f[m+n]=f[m+n-1] + f[m+n-2]
=f[m+n-2] + f[m+n-3] + f[m+n-2] = f[m+n-2] * 2 + f[m+n-3]
=f[m+n-3] * (2+1) + f[m+n-4] * 2 = f[m+n-3] * 3 + f[m+n-4] * 2
=f[m+n-4] * (3+2) + f[m+n-5] * 3 = f[m+n-4] * 5 + f[m+n-5] * 3
=f[m+n-5] * 8 + f[m+n-6] * 5 （发现规律了吗？）
=f[m+n-5] * f[6] + f[m+n-6] * f[5]
=f[m+n-x] * f[x+1] + f[m+n-x-1] * f[x]
=f[m] * f[n+1] + f[m-1] * f[n] （上一行的式子将n代入x）
引理三：gcd(f[n+m],f[m])=gcd(f[m],f[n])
gcd(f[n+m],f[m]) = gcd(f[m] * f[n+1] + f[m-1] * f[n],f[n]) （由引理二）
= gcd(f[n],f[m] * f[n+1]) （由辗转相除）
= gcd(f[m],f[n]) （由引理一，gcd(f[n],f[n+1])=1）
接下来，自认为很重要的最后一步：
（各路大神写的题解这块儿都太简略了，我都看不明白怎么弄出来的……感谢小伙伴帮忙，我才弄懂了这一步）
gcd(f[n],f[m]) = gcd(f[n-m],f[m]) = gcd(f[n%m],f[m])
此时我们发现f[]下标的变化与辗转相除的变化是一样的对不对
那么 原式就会如辗转相除一样变为gcd(f[gcd(n,m)],f[0])=gcd(f[gcd(n,m)],0)=f[gcd(n,m)]
感觉真是太神奇了！！
这条可爱的性质推出后，剩下的就很easy了
辗转相除法求gcd + 矩阵快速幂求斐波那契数列第x项
代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<string.h> 5 #define P 100000000 6 using namespace std; 7 8 typedef long long ll; 9 struct matrix{ 10 int a[2][2]; 11 void clear(){ 12 for(int i=0;i<2;i++) 13 for(int j=0;j<2;j++) 14 if(i==j) a[i][j]=1; 15 else a[i][j]=0; 16 } 17 void clear_all(){ 18 for(int i=0;i<2;i++) 19 for(int j=0;j<2;j++) a[i][j]=0; 20 } 21 matrix operator * (const matrix &b) const{ 22 matrix c; 23 for(int i=0;i<2;i++) 24 for(int j=0;j<2;j++){ 25 c.a[i][j]=0; 26 for(int k=0;k<2;k++) 27 c.a[i][j]=(c.a[i][j]+((ll)a[i][k]*b.a[k][j])%P)%P; 28 } 29 return c; 30 } 31 }; 32 33 matrix Power_Mod(matrix b,int x){ 34 matrix c; 35 c.clear(); 36 while(x){ 37 if(x&1) c=c*b; 38 b=b*b; 39 x>>=1; 40 } 41 return c; 42 } 43 int gcd(int x,int y){ 44 if(y==0) return x; 45 return gcd(y,x%y); 46 } 47 48 int main() 49 { 50 int n,m,w,i,j; 51 scanf("%d%d",&n,&m); 52 w=gcd(n,m); 53 54 matrix c,b; 55 b.clear_all(); 56 b.a[1][0]=b.a[0][1]=b.a[1][1]=1; 57 c.clear_all(); 58 c.a[0][1]=c.a[0][0]=1; 59 b=Power_Mod(b,w-1); 60 c=c*b; 61 62 printf("%d\n",c.a[0][0]); 63 64 return 0; 65 } View Code
转载于:https://www.cnblogs.com/lindalee/p/7706225.html
相关资源：数据结构—成绩单生成器