首页技术正文

洛谷 P1306 斐波那契公约数解题报告

开发者子寨技术 2022年11月21日

0 收藏 460 点赞 3,438 浏览 1270 个字

P1306 斐波那契公约数

题意：求$Fibonacci$数列第$n$项和第$m$项的最大公约数的最后8位。

数据范围：$1<=n,m<=10^9$

一些很有趣的性质

引理1：$F_{(a,b)}=(F_a,F_b)$

在证明引理1之前，我们得先证明引理2和引理3

引理2：$F_{m+n}=F_m*F_{n+1}+F_{m-1}*F_n=F_{m+1}*F_n+F_m*F_{n-1}$

证明：

设正整数$a>b$

$F_a$

$=F_{a-1}+F_{a-2}$

$=2*F_{a-2}+F_3$

$=3*F_{a-3}+2*F_{a-4}$

$=F_4*F_{a-3}+F_3*F_{a-4}$

$=…$

$=F_b*F_{a-b+1}+F_{b-1}*F_{a-b}$

引理3：$(F_n,F_{n+1})=1$

证明：

$(F_{n+1},F_n)$

$=(F_{n+1}-f_n,F_n)$

$=(F_{n-1},F_n)$

$=…$

$=(F_4,F_3)$

$=1$

证明引理1：

对于$F_{(a,b)}=(F_a,F_b)$

右边

$=(F_b*F_{a-b+1}+F_{b-1}*F_{a-b},F_b)$

$=(F_{b-1}*F_{a-b},F_b)$

$=(F_{a-b},F_b)$

即相当于坐标版的gcd了

最后等于$(F_{(a-b)},F_0)$

直接上矩阵快速幂一顿操作就行了

Code：

#include <cstdio>
#include <cstring>
#define ll long long
const ll mod=100000000;
ll m,n;
ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}
struct matrix
{
    ll dx[3][3];
    matrix()
    {
        memset(dx,0,sizeof(dx));
    }
    matrix friend operator *(matrix n1,matrix n2)
    {
        matrix n3;
        for(int i=1;i<=2;i++)
            for(int j=1;j<=2;j++)
                for(int k=1;k<=2;k++)
                    n3.dx[i][j]=(n3.dx[i][j]+n1.dx[i][k]*n2.dx[k][j])%mod;
        return n3;
    }
}base,s;
matrix quick_pow(matrix d,ll k)
{
    matrix f;
    f.dx[1][1]=f.dx[2][2]=1;
    while(k)
    {
        if(k&1)
            f=f*d;
        d=d*d;
        k>>=1;
    }
    return f;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    ll k=gcd(n,m);
    base.dx[1][1]=base.dx[1][2]=base.dx[2][1]=s.dx[1][1]=s.dx[1][2]=1;
    printf("%lld\n",quick_pow(base,k-1).dx[1][1]);
    return 0;
}