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;
}