【题解】The GCD of Fibonacci Numbers

题目

思路

重要性质： $\gcd(fib_n,fib_m) = fib_\gcd(n,m)$ ，当中 $f_{n}$ 表示斐波那契数列的第 $n$ 项。

题目中保证了 $\gcd(n,m) \leq 45$ 直接递推求就可以了。

$Code$

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>

typedef long long ll;
ll t,n,m,fib[47];

inline void read(ll &T) {
    ll x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    T=f?-x:x;
}

ll gcd(ll a,ll b) {
    return b?gcd(b,a%b):a;
}

int main() {
    read(t);fib[1]=1,fib[2]=1,fib[3]=2;
    for(int i=4;i<=46;++i) fib[i]=fib[i-1]+fib[i-2];
    while(t--) {
        read(n),read(m);
        if(m>n) std::swap(n,m);
        std::cout<<fib[gcd(n,m)]<<'\n';
    }
    return 0;
}