对于Fibonacci数列：1,1,2,3,5,8,13......大家应该很熟悉吧~~~但是现在有一个很“简单”问题：第n项和第m项的最大公约数是多少？
Update：加入了一组数据。
输入格式：
两个正整数n和m。（n,m<=10^9）
注意：数据很大
输出格式：
Fn和Fm的最大公约数。
由于看了大数字就头晕，所以只要输出最后的8位数字就可以了。
用递归&递推会超时
用通项公式也会超时
code
#include<stdio.h> #include<string.h> #include<algorithm> #define ll long long using namespace std; const int P=1e8; struct node { ll mp[3][3]; int h,l; }p,ans; int gcd(int x,int y) { if(x<y) swap(x,y); if(x%y==0) return y; else return gcd(y,x%y); } node mul(node x,node y) { node tep; memset(&tep,0,sizeof(tep)); for(int i=0;i<x.h;++i) for(int j=0;j<y.l;++j) for(int k=0;k<x.l;++k) tep.mp[i][j]=(tep.mp[i][j]+x.mp[i][k]*y.mp[k][j])%P; tep.h=x.h,tep.l=y.l; return tep; } int juc(ll k) { ans.mp[0][0]=ans.mp[0][1]=1; ans.h=1,ans.l=2; p.mp[0][0]=p.mp[0][1]=p.mp[1][0]=1; p.h=p.l=2; while(k) { if(k&1) ans=mul(ans,p); p=mul(p,p); k>>=1; } return ans.mp[0][0]; } int main() { int n,m; scanf("%d%d",&n,&m); int d=gcd(n,m); if(d<=2) printf("1"); else printf("%d",juc(d-2)); return 0; }
原文：https://www.cnblogs.com/qseer/p/9744514.html