【luogu P1306 斐波那契公约数】 题解

题目链接：https://www.luogu.org/problemnew/show/P1306#sub

gcd（f[m],f[n]） = f[gcd(m,n)]

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 1000001;
long long n, m;
long gcd(long long x, long long y)
{
    if(x%y == 0) return y;
    else return gcd(y,x%y);
}
long long f[maxn] = {0,1,1};
int main()
{
    scanf("%lld%lld",&n,&m);
    long long mn = gcd(n,m);
    
    for(int i = 3; i <= mn; i++)
    f[i] = (f[i-1] + f[i-2])%100000000;
    
    printf("%lld",f[mn]);
}