洛谷 P1306 斐波那契公约数

迷南。 2021-12-18 07:43 202阅读 0赞

## [https://www.luogu.org/problem/show?pid=1306][https_www.luogu.org_problem_show_pid_1306] ##

## 题目描述 ##

对于Fibonacci数列：1,1,2,3,5,8,13......大家应该很熟悉吧~~~但是现在有一个很“简单”问题：第n项和第m项的最大公约数是多少？

## 输入输出格式 ##

输入格式：

两个正整数n和m。（n,m<=10^9）

注意：数据很大

输出格式：

Fn和Fm的最大公约数。

由于看了大数字就头晕，所以只要输出最后的8位数字就可以了。

## 输入输出样例 ##

输入样例\#1：

4 7

输出样例\#1：

## 说明 ##

用递归&递推会超时

用通项公式也会超时

令 f\[n\]=a,f\[n+1\]=b

f\[n+2\]=a+b

f\[n+3\]=a+2b

f\[n+4\]=2a+3b

……

f\[m\]=f\[m-n-1\]\*a+f\[m-n\]\*b

由欧几里得定理得：gcd（a，b）=gcd（a，b%a）

所以gcd（f\[n\],f\[m\]）

=gcd（f\[n\],f\[m\]%f\[n\]）

=gcd（f\[n\],f\[m-n\]\*b）

=gcd（a,f\[m-n\]\*b）

因为gcd（a，b）=1

所以上式

=gcd（a，f\[m-n\]）

=gcd（f\[n\],f\[m-n\]）

递归，所以上式

=gcd（f\[n\],f\[m%n\]）

所以gcd（f\[n\],f\[m\]）=f\[gcd（n，m）\]

矩阵乘法优化

#include<cstdio>
    #include<cstring>
    using namespace std;
    typedef long long LL;
    LL t[2][2],ans[2][2],r[2][2];
    const int mod=1e8;
    int gcd(int a,int b)
    {
        return !b ? a : gcd(b,a%b);
    }
    void mul(LL a[2][2],LL b[2][2])
    {
        memset(r,0,sizeof(r));
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                    r[i][j]+=a[i][k]*b[k][j],r[i][j]%=mod;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                a[i][j]=r[i][j];
    }
    int main()
    {
        int a,b;
        scanf("%d%d",&a,&b);
        int p=gcd(a,b);
        t[0][0]=t[0][1]=t[1][0]=1;;
        ans[0][0]=ans[0][1]=1;
        if(p==2 || p==1) { printf("1"); return 0; }
        p-=2;
        while(p)
        {
            if(p&1) mul(ans,t);
            mul(t,t); p>>=1;
        }
        printf("%lld",ans[0][0]);
    }

转载于:https://www.cnblogs.com/TheRoadToTheGold/p/7499503.html

[https_www.luogu.org_problem_show_pid_1306]: https://www.luogu.org/problem/show?pid=1306