题目链接:
A. 再战斐波那契
单点时限: 1.0 sec
内存限制: 512 MB
小z 学会了斐波那契和 gcd 后,老师又给他出了个难题,求第N个和第M个斐波那契数的最大公约数,这可难倒了小z ,不过在小z 的再三请求下,老师又告诉他了个条件,gcd(N,M)∈[1,90]。
可是,笨拙的小z 还是不会,于是请求你帮他解答这个问题。
输入格式
输入包括 T 组,T∈[1,10].
接下来 T 行,每行两个整数 N,M, 表示斐波那契的第 N 项和第 M 项,(N,M∈[1,1018]).
输出格式
输出包含 T 行,每行输出一个整数.
分析:
任意两个斐波那契数的最大公约数等于,这两个数的项数的最大公约数所代表的哪一项的斐波那契数
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100;
LL fib[N];
LL gcd(LL a, LL b)
{
return !b ? a : gcd(b, a%b);
}
int main()
{
fib[0] = 0;
fib[1] = 1;
fib[2] = 1;
for(int i=3; i<N; i++)
fib[i] = fib[i-1] + fib[i-2];
int t;
scanf("%d", &t);
while(t--)
{
LL n, m;
scanf("%lld %lld", &n, &m);
LL gcdnm = gcd(n, m);
printf("%lld\n", fib[gcdnm]);
// for(int i=1; i<=19; i++)
// {
// printf("%lld ", gcd(fib[i], fib[20]));
// if(i%10 == 0)
// printf("\n");
// }
}
return 0;
}