ZeroJudge 解題筆記：e272. gcd(Fm,Fn)

作者：王一哲
日期：2025年9月18日


ZeroJudge 題目連結：e272. gcd(Fm,Fn)

解題想法

這題考數學，必須運用費氏數列的特性 $$ gcd(F_m, F_n) = F_{gcd(m, n)} $$ 如果直接計算 $F_m, F_n$ 的數值再取 $gcd$，在 $m, n$ 極大的狀況下會超時。

Python 程式碼

使用時間約為 0.3 s，記憶體約為 4.6 MB，通過測試。

import sys, math

fib = [0]*94
fib[1] = 1
for i in range(2, 94):
    fib[i] = fib[i-1] + fib[i-2]

for line in sys.stdin:
    a, b = map(int, line.split())
    print(fib[math.gcd(a, b)])

C++ 程式碼

使用時間約為 42 ms，記憶體約為 92 kB，通過測試。

#include <cstdio>
#include <algorithm>
typedef unsigned long long LL;
using namespace std;

int main() {
    LL fib[94] = {0};
    fib[1] = 1;
    for(int i=2; i<=93; i++) fib[i] = fib[i-1] + fib[i-2];
    int a, b;
    while(scanf("%d %d", &a, &b) != EOF) printf("%llu\n", fib[__gcd(a, b)]);
    return 0;
}