问题标题: 酷町堂：3386

对于Fibonacci数列：1,1,2,3,5,8,13…，求第n项和第m项的最大公约数是多少？

输入描述 Input Description

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

输出描述 Output Description

Fn和Fm的最大公约数。只要输出最后的8位数字就可以了。

RE 0

#include<iostream>
using namespace std;
long long f[100001];
int Fibonacci(int n){
    f[1]=1;
    f[2]=1;
    for(int i=3;i<=n;i++){
        f[i]=f[i-1]+f[i-2];
    }
    return f[n];
}
int main(){
    int x,y,r;
    cin>>x>>y;
    int a=Fibonacci(x),b=Fibonacci(y);
    while(a%b!=0){
        r=a%b;
        a=b;
        b=r;
    }
    cout<<b;
    return 0;
}