题目描述
对于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<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<set> #include<vector> #include<cmath> #include<map> #define mod 100000000 const 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; }