题解 P1306 【斐波那契公约数】

· · 题解

　　本题其实并不难，开始被题意吓到了，结果后面写出了式子都没看出来（手动滑稽～）。 发现自己推结论的方法不太一样，所以发发题解。

\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

代码：

// 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;
}