最大公約數：輾轉相除法（歐幾里得算法）求解

問題描述

輸入多組兩個正整數，輸出它們的最大公約數 (GCD)。

算法：歐幾里得算法

核心性質：gcd(a, b) = gcd(b, a % b)。
遞歸/迭代直到餘數為 0，當前除數即為 GCD。

代碼實現 (C/C++)

#include <cstdio>
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
int main() {
    int m, n;
    while (scanf("%d %d", &m, &n) == 2) {
        printf("%d\n", gcd(m, n));
    }
    return 0;
}

複雜度

• 時間：O(log min(a,b))，極快。
• 空間：遞歸深度 O(log n)，可改迭代為 O(1)。

關鍵點

• 輾轉相除法是求 GCD 的標準高效算法。
• 注意輸入多組，直到 EOF。
• 可處理大整數（用 long long 或大整數庫）。

這是最基礎的數論算法，代碼極簡，效率極高，是無數進階算法的基石。