https://www.luogu.org/problem/show?pid=1306
题目描述
对于Fibonacci数列：1,1,2,3,5,8,13......大家应该很熟悉吧~~~但是现在有一个很“简单”问题：第n项和第m项的最大公约数是多少？
输入输出格式
输入格式：
两个正整数n和m。（n,m<=10^9）
注意：数据很大
输出格式：
Fn和Fm的最大公约数。
由于看了大数字就头晕，所以只要输出最后的8位数字就可以了。
输入输出样例
输入样例#1：
4 7
输出样例#1：
1
说明
用递归&递推会超时
用通项公式也会超时
令 f[n]=a,f[n+1]=b
f[n+2]=a+b
f[n+3]=a+2b
f[n+4]=2a+3b
……
f[m]=f[m-n-1]*a+f[m-n]*b
由欧几里得定理得：gcd（a，b）=gcd（a，b%a）
所以gcd（f[n],f[m]）
=gcd（f[n],f[m]%f[n]）
=gcd（f[n],f[m-n]*b）
=gcd（a,f[m-n]*b）
因为gcd（a，b）=1
所以上式
=gcd（a，f[m-n]）
=gcd（f[n],f[m-n]）
递归，所以上式
=gcd（f[n],f[m%n]）
所以gcd（f[n],f[m]）=f[gcd（n，m）]
矩阵乘法优化
#include<cstdio> #include<cstring> using namespace std; typedef long long LL; LL t[2][2],ans[2][2],r[2][2]; const int mod=1e8; int gcd(int a,int b) { return !b ? a : gcd(b,a%b); } void mul(LL a[2][2],LL b[2][2]) { memset(r,0,sizeof(r)); for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) r[i][j]+=a[i][k]*b[k][j],r[i][j]%=mod; for(int i=0;i<2;i++) for(int j=0;j<2;j++) a[i][j]=r[i][j]; } int main() { int a,b; scanf("%d%d",&a,&b); int p=gcd(a,b); t[0][0]=t[0][1]=t[1][0]=1;; ans[0][0]=ans[0][1]=1; if(p==2 || p==1) { printf("1"); return 0; } p-=2; while(p) { if(p&1) mul(ans,t); mul(t,t); p>>=1; } printf("%lld",ans[0][0]); }