The GCD of Fibonacci Numbers

链接：https://ac.nowcoder.com/acm/contest/3674/A

The Fibonacci sequence is the sequence of numbers such that every element is equal to the sum of the two previous elements, except for the first two elements f0 and f1 which are respectively zero and one. The first few numbers in the Recaman's Sequence is 0,1,1,2,3,5,8,... The ith Fibonacci number is denoted fi.

The largest integer that divides both of two integers is called the greatest common divisor of these integers. The greatest common divisor of a and b is denoted by gcd(a,b).

Two positive integers m and n are given,you must compute the GCD(fm,fn).

输入描述:

The first linecontains one integer T（T ≤ 100）,the number of test cases.
For each test case,there are two positive integers m and n in one line. (1 ≤m,n ≤ 231 , GCD(m,n) ≤ 45)

输出描述:

 Foreach the case, your program will outputthe GCD(fm,fn).

示例1

输入

复制

4
1 2
2 3
2 4
3 6

输出

复制

1
1
1
2

一开始俺以为要用矩乘写，没想到看到别人的代码原来只要求出第gcd(n,m)项斐波那契数列就行

代码：

#include<bits/stdc++.h>
using namespace std;
int T;
long long a,b,f[110];
long long gcd(long long a,long long b){
    if (!b) return a;
    return gcd(b,a%b);
}
int main(){
    f[0]=0;
    f[1]=1;
    for(int i=2;i<=45;i++) 
        f[i]=f[i-1]+f[i-2];
    scanf("%d",&T);
    while (T--){
        scanf("%lld%lld",&a,&b);
        printf("%lld\n",f[gcd(a,b)]);
    }
}