TLE RE TLE RE MLE TLE

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef string sg;
typedef long lg;
typedef double de;
typedef char ch;
typedef long long ll;
typedef bool bl;
typedef unsigned int ui;

int _gcd(int a,int b){
	for(int i=min(a,b);i>0;i--){
		if((a%i==0)&&(b%i==0)){
			return i;
			break;
		}
	}
}

int main()
{
	long long n,m,fn,fm;
	cin>>n>>m;
	int x[max(n,m)]={1,1};
	for(int i=2;i<max(n,m);i++){
		x[i]=x[i-1]+x[i-2];
		if(i==min(n,m)-1){
			fn=x[i];
		}
	}
	fm=x[max(n,m)-1];
	cout<<_gcd(fn,fm)%int(pow(10,8));
	return 0;
}