The GCD of Fibonacci Numbers

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;
} 
上一篇:POJ 3070 Fibonacci


下一篇:入门训练 BEGIN-4 Fibonacci数列