gcd题目

样例有误 应该输出 0 1000000006

刚看到这个题，一脸懵逼。

打个表

观察一下

发现，除了做一次gcd时，如果做 t 次gcd，那么和最小的 a 和 b 分别是斐波那契数列的f[t+1]和f[t+2]。由于k很大，用矩阵快速幂即可。

而做一次就是 1 1（需要特判）

打表程序

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int gcd(int a,int b,int t)
{
    if(a>b) swap(a,b);
    if(a==) return t;
    return gcd(b%a,a,t+);
}
int main()
{
    int p=;
    while(p<=)
    {
        int f=;
        for(int i=;i<=;i++)
        {
            for(int j=;j<=;j++)
            {
                if(gcd(i,j,)==p)
                printf("%d %d 做%d次gcd\n",i,j,p),f=;
                if(f) break;
            } 
            if(f==) {p++;break;}
        }
    }
    return ; 
}
           

题目代码

#include<iostream>
#include<cstdio>
#include<vector>
#define LL long long
#define MOD 1000000007
using namespace std;
LL A[][]={,,,
             ,,,
             ,,,};
LL k,ans;
LL f[][],bak[][];
void Fast_Pow(LL p)
{
    while(p)
    {
        if(p%2) 
        {
            for(int i=;i<=;i++)
            for(int j=;j<=;j++)
            bak[i][j]=f[i][j],f[i][j]=;

            for(int i=;i<=;i++)
            for(int j=;j<=;j++)
            for(int k=;k<=;k++)
            (f[i][j]+=(bak[i][k]*A[k][j])%MOD)%=MOD;
        }
        for(int i=;i<=;i++)
        for(int j=;j<=;j++)
        bak[i][j]=A[i][j],A[i][j]=;

        for(int i=;i<=;i++)
        for(int j=;j<=;j++)
        for(int k=;k<=;k++)
        (A[i][j]+=(bak[i][k]*bak[k][j])%MOD)%=MOD;
        p/=;
    }
    printf("%lld %lld\n",f[][],f[][]);
}
int main()
{
    freopen("gcd.in","r",stdin);
    freopen("gcd.out","w",stdout);
    scanf("%lld",&k);
    f[][]=,f[][]=;
    if(k==) printf("1 1\n");
    else Fast_Pow(k);
    return ;
}
           

证明是这样的：

①如果有一步辗转相除 (a,b) → (b,a − k ∗ b),k > 1，一定

能找到更优的 (b + a mod b,b) （这是最优），即本题只考虑辗转相减

②如果一系列得到数对 (0,t),t > 1，一定对应一个结束在

(0,1)（这是最优） 的更优解