题解 P1306 【斐波那契公约数】
浅色调
2018-04-03 15:39:37
本题其实并不难，开始被题意吓到了，结果后面写出了式子都没看出来（手动滑稽～）。
发现自己推结论的方法不太一样，所以发发题解。
### $\quad$方法：结论+矩阵加速
### $\quad$结论：$$gcd(F[n],F[m])=F[gcd(n,m)]$$
### $\quad$证明：
我们设$n<m$，$F[n]=a$和$F[n+1]=b$。
则$F[n+2]=a+b,F[n+3]=a+2b,…F[m]=F[m-n-1]a+F[m-n]b$
$\because \quad$ $F[n]=a,F[n+1]=b,F[m]=F[m-n-1]a+F[m-n]b$
$\therefore \quad$ $F[m]=F[m-n-1]*F[n]+F[m-n]*F[n+1]$
又$\because \quad$ $gcd(F[n],F[m])=gcd(F[n],F[m-n-1]*F[n]+F[m-n]*F[n+1])$
而$F[n]|F[m-n-1]*F[n]$
$\therefore \quad$ $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+1]-F[n])=gcd(F[n],F[n-1])$
$=gcd(F[n-2],F[n-1])$
$……$
$=gcd(F[1],F[2])=1$
$\therefore \quad$ $gcd(F[n],F[n+1])=1$
由引理知：
$F[n],F[n+1]$互质
而$gcd(F[n],F[m])=gcd(F[n],F[m-n]*F[n+1])$
$\therefore \quad$ $gcd(F[n],F[m])=gcd(F[n],F[m-n])$
即$gcd(F[n],F[m])=gcd(F[n],F[m\;mod\;n])$
继续递归，将$m1=m\;mod\;n$，则$gcd(F[n],F[m])=gcd(F[n\;mod\;m1],F[m1])$
$…$
不难发现，整个递归过程其实就是在求解$gcd(n,m)$
最后递归到出现$F[0]$时，此时的$F[n]$就是所求gcd。
$$\therefore \quad gcd(F[n],F[m])=F[gcd(n,m)]$$
于是本题就转为求$gcd(n,m)$，然后求斐波拉契数列的$F[gcd(n,m)]$项后8位（即对100000000取模）。
至于矩阵的构造：
初始矩阵 $\begin{bmatrix} F[2]=1 & F[1]=1\end{bmatrix} $
以及中间矩阵
$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$
注意矩阵数组开long long！！
#### $\quad$欢迎来踩博客（转载请注明出处）：[five20](http://www.cnblogs.com/five20/p/8708445.html)
### 代码：
```cpp
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define mem(p) memset(&p,0,sizeof(p))
using namespace std;
const ll mod=1e8;
ll n,m;
struct mat{ll a[3][3],r,c;};
il mat mul(mat x,mat y)
{
mat p;
mem(p);
for(int i=0;i<x.r;i++)
for(int j=0;j<y.c;j++)
for(int k=0;k<x.c;k++)
p.a[i][j]=(p.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
p.r=x.r,p.c=y.c;
return p;
}
il void fast(ll k)
{
mat p,ans;
mem(p),mem(ans);
p.r=p.c=2;
p.a[0][0]=p.a[0][1]=p.a[1][0]=1;
ans.r=1,ans.c=2;
ans.a[0][0]=ans.a[0][1]=1;
while(k)
{
if(k&1)ans=mul(ans,p);
p=mul(p,p);
k>>=1;
}
cout<<ans.a[0][0];
}
il ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main()
{
ios::sync_with_stdio(0);
cin>>n>>m;
n=gcd(n,m);
if(n<=2)cout<<1;
else fast(n-2);
return 0;
}
```