题目描述

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

输入输出格式

输入格式：

 

两个正整数n和m。（n,m<=10^9）

注意：数据很大

 

输出格式：

 

Fn和Fm的最大公约数。

由于看了大数字就头晕，所以只要输出最后的8位数字就可以了。

 

输入输出样例

输入样例#1：

4 7

输出样例#1：

1

说明

用递归&递推会超时

用通项公式也会超时

 

 

啊啊啊！！！

有没有看到这个题就头晕的感觉！

哎，其实我也晕

来跟你说个性质，你就会发现这个题其实很简单！

 

斐波那契数列（Fibonacci Sequence）具有以下特征：gcd(fn,fm)=f(gcd(n,m))

既第n项和第m项的公倍数=第n和m的公倍数项

 

什么鬼！有没有感觉很简单？

需不需要证明一下？？

好吧，那就证明一下吧

证明首先，斐波那契数列相邻项的gcd=1。假设不为1的话，可以推出之前所有相邻项gcd均不为1，但gcd(f(1),f(2))=gcd(1,1)=1，矛盾，所以相邻项gcd=1。然后，不妨设n

 

 

下面就来看一看代码吧！

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int f[5001][5001],len[5001];int read(){    int x=0,f=1;    char ch=getchar();    while(ch<'0'||ch>'9')    {        if(ch=='-')          f=-1;        ch=getchar();    }    while(ch>='0'&&ch<='9')    {        x=10*x+ch-'0';        ch=getchar();    }    return f*x; } int gcd(int a,int b){    return b==0 ? a:gcd(b,a%b);}void w(int a,int b,int c){    for(int i=1;i<=max(len[b],len[c]);i++)    {        f[a][i]+=f[b][i]+f[c][i];        if(f[a][i]>9)        {            f[a][i+1]=f[a][i]/10;            f[a][i]%=10;            len[a]=max(len[a],i+1);        }        else len[a]=max(len[a],i);     }}int main(){    int c,n=read(),m=read();    c=gcd(n,m);//先求最大公约数再求斐波那契数    f[1][1]=1;    f[2][1]=1;    len[0]=1;    len[1]=1;    for(int i=3;i<=c;i++)    {        w(i,i-1,i-2);    }    for(int i=min(len[c],8);i>=1;i--)//注意：题目让输出后8位数      cout<