题目大意：给你一个n，m（1<=n,m<=1e9），求__gcd（F[n]，F[m]）%1e8.
首先我在这里提出一个数论定理：__gcd（F[n]，F[m]）=F[__gcd（n，m）]。
其实在知道这个数论定理后这题就变得非常容易了，只需要求出n,m的最大公约数，然后利用矩阵加速求F[__gcd（n，m）]对1e8取模即可。
但是这个定理为什么是正确的呢？
证明如下：
设n<m，且F[n]=a，F[n+1]=b
F[n+2]=a+b
F[n+3]=a+2*b=F[n]+2*F[n+1]
F[n+4]=2*a+3*b=2*F[n]+3*F[n+1]
F[n+5]=3*a+5*b=3*F[n]+5*F[n+1]
...
不难发现 F[n+x]=F[x-1]*F[n]+F[x]*F[n+1]
F[m]=F[m-n-1]*F[n]+F[m-n]*F[n+1]
所以 __gcd（F[n]，F[m]）=__gcd（F[n]，F[m-n-1]*F[n]+F[m-n]*F[n+1]）;
因为 F[m-n-1]*F[n]%F[n]==0
所以 __gcd（F[n]，F[m]）=__gcd（F[n]，F[m-n]*F[n+1]）;
证明之路似乎在这里卡住了，因为这个式子很难再去化简，而单从这个式子也很难看出什么东西，这时我们就需要另一个引理：__gcd（F[n]，F[n+1]）=1；
关于引理的证明比较简单：
__gcd（F[n]，F[n+1]）=__gcd（F[n]，F[n]+F[n-1]）
=__gcd（F[n]，F[n-1]）
=__gcd（F[n-1]+F[n-2]，F[n-1]）
=__gcd（F[n-2]，F[n-1]）
......
=__gcd（F[1]，F[2]）=1
我们在得出__gcd（F[n]，F[n+1]）=1 后就可以继续对__gcd（F[n]，F[m]）=__gcd（F[n]，F[m-n]*F[n+1]）进行化简
最后__gcd（F[n]，F[m]）=__gcd（F[n]，F[m-n]）
=__gcd（F[n]，F[m%n]）
......
=F[__gcd（n，m）]
于是，证明完成~
下面放上这题AC代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> PII; const int MAXN = 1e6+10; const double EPS = 1e-12; const ll mod = 1e8; ll n,mm; struct Mat{ ll m[5][5]; Mat(){ memset(m,0,sizeof(m)); } inline void build(){ for(int i=1;i<=2;i++)m[i][i]=1; } }a; Mat Mul(Mat x,Mat y){ Mat c; for(int i=1;i<=2;i++) for(int j=1;j<=2;j++) for(int k=1;k<=2;k++) c.m[j][i]=(c.m[j][i]+x.m[j][k]*y.m[k][i]%mod)%mod; return c; } Mat poww(Mat x,ll y){ Mat aa;aa.build(); while(y){ if(y&1)aa=Mul(aa,x); x=Mul(x,x); y>>=1; } return aa; } int main() { scanf("%lld %lld",&n,&mm); ll p=__gcd(n,mm); a.m[1][1]=a.m[2][1]=a.m[1][2]=1; Mat ans=poww(a,p-1); printf("%lld",ans.m[1][1]); }