大家都知道斐波那契数列即：f(1)=1,f(0)=0,f(i)=f(i−1)+f(i−2)(i≥2)，现在请帮小码哥计算gcd(f(n),f(m))的值。
格式
输入格式：
第一行输入两个整数n,m(1≤n,m≤50000)。
输出格式：
输出一个整数代表gcd(f(n),f(m)) 结果对1000000取模。
样例 1
输入：
3 6
输出：
2
思路：斐波那契数列的最大公约数定理：gcd(F(m),F(n))=F(gcd(m,n))
代码：
#include <bits/stdc++.h> using namespace std; int n, m; int p = 1000000; int a[50005]; void f() { for (int i = 0; i < 50005; i++) { if (i == 0) a[i] = 0; else if (i == 1) a[i] = 1; else { a[i] = a[i - 1] + a[i - 2]; a[i] %= p; } } } int main() { cin >> n >> m; n %= p, m %= p; int x = __gcd(n, m); f(); cout << a[x]; }
