「洛谷P1306」斐波那契公约数 解题报告

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;
}
全部评论

相关推荐

#简历#先说一说我自己的想法,很多人都很排斥苍穹外卖,认为没什么技术点和含金量,但实际上我觉得恰恰相反,苍穹外卖虽然代码本身并不是你自身能力的证明,但是是作为一个新人学习时很好的跳板和原始框架,在这个框架上进行的改进可以很好的辐射到你自己的个人成果上,并作为你和面试官聊天的筹码大多数人的苍穹外卖只写增删改查,千篇一律,吸引不了面试官,所以这才让大家误以为只要是苍穹外卖就不要写进简历里这种误区,但实际上如果你在原有的层面上进行改进,并作为你的项目亮点和面试官介绍,告诉他你的苍穹外卖和别人的有什么不同,增加了哪些技术难点,这才显得你是完全自己理解了这个项目,并且有自己动手实践项目的能力,而不是就看了个课程就以为自己会了,就当成自己的了,如此一来,这反而成为你的加分项苍穹外卖为什么看的人最多,说明它好啊,如果它不好,为什么看的人还这么多,想清楚这个逻辑,我觉得要做的最重要的事,就是如何在原有框架上进行改进提效,比起听其他人的话重新搞一个项目性价比高得多,而且我亲测项目并没有成为我找到工作的阻碍,我投的大厂一大半都给我面试了,而且很多不止一个部门,退一万步说,当你手头没有其他项目的时候,有苍穹外卖总比什么都没有的好很多,不需要因为苍穹外卖有任何心理负担关于简历的任何部分都欢迎大家提意见,十分感谢大家,祝大家找实习+秋招顺利上岸,offer拿到手软#简历中的项目经历要怎么写##我的上岸简历长这样##最后再改一次简历##简历##简历被挂麻了,求建议#
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务