The GCD of Fibonacci Numbers
链接:The GCD of Fibonacci Numbers
题解:
\[
gcd(f_n,f_m)=f(gcd(n,m))
\]
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[50];
void Init(){
f[0] = 0;
f[1] = 1;
f[2] = 1;
f[3] = 2;
for(int i = 4; i <= 45; i++){
f[i] = f[i-1]+f[i-2];
}
}
int gcd(int a,int b){
if(b==0)
return a;
return gcd(b,a%b);
}
int main(void){
Init();
int t;
cin >> t;
while(t--){
int n,m;
cin >> n >> m;
cout<< f[gcd(n,m)] <<endl;
}
return 0;
}