我真的要哭死

作为一个萌新，我刚刚学会递归想来LG挑战一下，结果发现就这一道题还拿的准，于是怀着激动的心情点进去，刚进来就被描述吓着了，但还好，根据我的知识储备还是勉强看懂了，就当我以为胜利在前时，一个TLE把我吓蒙圈了，所以……

谁来帮帮我啊喂！！！！！！

用的是递归，C++的，求解！

#include<bits/stdc++.h>
using namespace std;
int fbnc(int x){
    if(x <= 1) return 1;
    return fbnc(x-1) + fbnc(x-2);
}
int gcd(int x, int y){
    if(x == y) return x;
    if(x > y) return gcd(y, x-y);
    if(y > x) return gcd(x, y-x);
} 
int main(){
    int a, b;
    cin >> a >> b;
    cout << gcd(fbnc(a),fbnc(b)) % 100000000;
    return 0;
}