P1306 斐波那契公约数

题目描述

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

输入输出格式

输入格式:

两个正整数n和m。(n,m<=10^9)
注意:数据很大

输出格式:

Fn和Fm的最大公约数。
由于看了大数字就头晕,所以只要输出最后的8位数字就可以了。

输入输出样例

输入样例#1:

4 7

输出样例#1:

1

说明

用递归&递推会超时
用通项公式也会超时


前置芝士

矩阵快速幂,更相减损术,欧几里得算法。

思路

初看此题,毫无头绪,其实并不难。

结论很简单,设\(f[i]\)表示斐波那契数列第\(i\)个,则有\(\gcd(f[i],f[j])=f[\gcd(i,j)]\)

为什么呢?

显然,当\(i=j\)时,结论成立。

假设\(i<j\),我们设\(f[i]=a,f[i+1]=b,f[i+2]=a+b...\)

很明显,\(f[j]=f[j-i]\times b+f[j-i-1]\times a\)

因此\(\gcd(f[i],f[j])=\gcd(f[i],f[j-i]\times f[i+1]+f[j-i-1]\times f[i])\)

\(\gcd(f[i],f[j])=\gcd(f[i],f[j-i]\times f[i+1])\)

引理:\(\gcd(f[i],f[i+1])=1\)

证明:

显然,\(\gcd(f[1],f[2])=1\)成立。

\(\gcd(f[2],f[3])=\gcd(f[2],f[3]-f[2])=\gcd(f[2],f[1])=1\)

\(\gcd(f[3],f[4])=\gcd(f[3],f[4]-f[3])=\gcd(f[3],f[2])=1\)

...

QED.

回到\(\gcd(f[i],f[j])=\gcd(f[i],f[j-i]\times f[i+1])\)这个式子,因为\(\gcd(f[i],f[i+1])=1\),因此\(\gcd(f[i],f[j])=\gcd(f[i],f[j-i]\times f[i+1])=\gcd(f[i],f[j-i])\)

发现了吧?这和更相减损术的\(\gcd(i,j)=\gcd(i,i-j)\)蜜汁相似,没错,就是公约数!\(\gcd(f[i],f[j])\)就等于\(f[\gcd(i,j)]\)

然后用矩阵快速幂求出\(f[\gcd(n,m)]\)即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define Re register

int N, M;

int gcd( int x, int y ){ return y ? gcd( y, x % y ) : x; }

int a[3][3], b[3][3], c[3][3];

inline void Times( int a[3][3], int b[3][3] ){
    memset( c, 0, sizeof c );
    for ( int i = 1; i <= 2; ++i )
        for ( int k = 1; k <= 2; ++k )
            for ( int j = 1; j <= 2; ++j )
                c[i][j] = (int)( ( c[i][j] + 1ll * a[i][k] * b[k][j] ) % 100000000 );
}

int main(){
    scanf( "%d%d", &N, &M );
    N = gcd( N, M ) - 2;
    if ( N <= 0 ){ printf( "1\n" ); return 0; }
    a[1][1] = a[1][2] = b[1][1] = b[1][2] = b[2][1] = 1;
    for ( int i = N; i; i >>= 1 ){
        if ( i & 1 ) Times( a, b ), memcpy( a, c, sizeof a );
        Times( b, b ), memcpy( b, c, sizeof b );
    }
    printf( "%d\n", a[1][1] );
    return 0;
}