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)（這是最優） 的更優解