zcmimi's blog
avatar
zc
2020-10-14 18:06:50
  • 本文总阅读量

查看原题

点击跳转

结论: \gcd(f_n,f_m)=f_{\gcd(n,m)},然后矩阵快速幂加速即可

证明:

m>n

引理:

  • \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,f_{n+1})=\gcd(f_n,f_{n-1})=\dots=\gcd(f_2,f_1)=1

  • f_{n+m}=f_nf_{m-1}+f_{n+1}f_m

    数学归纳法:

    1. n=m=1时,成立
    2. 假设m,n\le k时成立,当n=k+1时:

      \begin{aligned} f_{n+m} &=f_{m+(k+1)}=f_{k+(m+1)}\\ &=f_mf_{k-1}+f_{m+1}f_k\\ &=f_mf_{k-2}+f_{m+1}f_k + f_{m+1}f_{k-1}+f_{m+2}f_k\\ &=f_{m+1}(f_{k}+f_{k-1})+f_{m}(f_{k-1}+f_{k-2})\\ &=f_kf_m+f_{k+1}f_{m+1} \end{aligned}

  • \gcd(f_{n+m},f_n)=\gcd(f_n,f_m)

    \begin{aligned} \gcd(f_{n+m},f_n) &=\gcd(f_nf_{m-1}+f_{n+1}f_m,f_n)\\ &=\gcd(f_{n+1}f_m,f_n)\\ &=\gcd(f_{n+1},f_n)\cdot\gcd(f_m,f_n)\\ &=\gcd(f_m,f_n) \end{aligned}

\begin{aligned} \gcd(f_n,f_m) &=\gcd(f_n,f_{m-n+n})\\ &=\gcd(f_n,f_{m-n}f_{n-1}+f_{m-n+1}f_n)\\ &=\gcd(f_n,f_{m-n}f_{n-1}) \end{aligned} \\ \because \gcd(f_{n},f_{n+1})=1\\ \therefore \gcd(f_n,f_{m-n}f_{n-1})=\gcd(f_n,f_{m-n})

这样一直碾转相减下去,就是f_{\gcd(n,m)}

#include<bits/stdc++.h>
const int P=100000000;
int n,m;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
struct mat{
    int a[2][2];
    mat operator*(const mat&x)const{
        mat c;memset(c.a,0,sizeof c.a);
        for(int k=0;k<2;++k)
            for(int i=0;i<2;++i)
                for(int j=0;j<2;++j)
                    (c.a[i][j]+=1ll*a[i][k]*x.a[k][j]%P)%=P;
        return c;
    }
}A,B;
int main(){
    scanf("%d%d",&n,&m);
    n=gcd(n,m);
    A={
        1,0,
        1,0
    };
    B={
        1,1,
        1,0
    };
    for(--n;n;n>>=1,B=B*B)if(n&1)A=A*B;
    printf("%d\n",A.a[0][0]);
}
LG 1306 斐波那契公约数
comment评论
Search
search