ZeroJudge 解題筆記：b537. 分數運算-1

作者：王一哲
日期：2026年5月5日


ZeroJudge 題目連結：b537. 分數運算-1

解題想法

規則1，$f(1) = 1$，此時 $a = 1, b = 1$。 規則2，若 $k$ 為偶數，則 $$ f(k) = 1 + f(k/2) = \frac{a}{b} > 1 ~\Rightarrow~ f(k/2) = \frac{a - b}{b}, ~ a > b $$ 規則3，若 $k$ 為奇數，則 $$ f(k) = \frac{1}{f(k-1)} = \frac{a}{b} < 1 ~\Rightarrow~ f(k-1) = \frac{b}{a}, ~ a < b $$ 根據以上的3條規則寫自訂函式 find_k，呼叫時代入 a, b。由規則1寫遞迴出口，當 $a == b$ 時回傳 $1$。接下來依照 $a, b$ 的大小決定遞迴的方式，若 $a > b$，依照規則2，回傳 2*find_k(a-b, b)；若 $a < b$，依照規則3，回傳 find_k(b, a) + 1。

Python 程式碼

使用時間約為 16 ms，記憶體約為 8.5 MB，通過測試。

def find_k(a, b):
    if a == b:
        return 1
    if a > b:
        return 2 * find_k(a-b, b)
    else:
        return find_k(b, a) + 1

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        x = int(data[ptr])
        y = int(data[ptr+1])
        ptr += 2
        result.append(f"{find_k(x, y):d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

使用時間約為 14 ms，記憶體約為 8.4 MB，通過測試。

def find_k(a, b):
    if a == b:
        return 1
    if a > b:
        return 2 * find_k(a-b, b)
    else:
        return find_k(b, a) + 1

def solve():
    import sys
    
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        x = int(data[ptr])
        y = int(data[ptr+1])
        ptr += 2
        print(find_k(x, y))

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 1 ms，記憶體約為 1.5 MB，通過測試。

#include <cstdio>
typedef unsigned long long LL;

LL find_k(LL a, LL b) {
    if (a == b) return 1;
    if (a > b) {
        return 2 * find_k(a - b, b);
    } else {
        return find_k(b, a) + 1;
    }
}

int main() {
    LL a, b;
    while(scanf("%lld %lld", &a, &b) != EOF) {
        printf("%lld\n", find_k(a, b));
    }
    return 0;
}