GCD & LCM最大公因數

01為什麼需要它

看到這些關鍵字就想到它：最大公因數、最小公倍數、約分、通分、比例、週期何時重合、整除、ax + by = c 有沒有整數解、模數不是質數時的反元素、陣列所有數的公因數。

02核心概念

輾轉相除法（歐幾里得演算法）只靠一個等式：gcd(a, b) = gcd(b, a mod b)。理由是 a mod b = a − q·b：任何同時整除 a 和 b 的數，一定也整除 a − q·b；反過來，同時整除 b 和餘數 r 的數，也整除 a = q·b + r。兩組數的公因數集合完全相同，最大的那個當然也相同。每做一次，數字就變小，直到餘數為 0，而 gcd(g, 0) = g。整個過程從不需要知道 a、b 的質因數，這是它比「分解質因數再取共同部分」快得多的原因。

為什麼快：看連續兩步 (a, b) → (b, r) → (r, r′)。若 b ≤ a/2，則 r < b ≤ a/2；若 b > a/2，商只能是 1，r = a − b < a/2。所以每兩步第一個數至少減半，除法次數是 O(log min(a, b))。最壞情況是相鄰的費氏數，每次商都是 1、縮得最慢，例如 gcd(89, 55) 要 9 次除法。迴圈版只用兩個變數，空間 O(1)；遞迴版要 O(log) 的呼叫堆疊。最小公倍數靠 gcd(a, b) × lcm(a, b) = a × b 得到，寫成 a / gcd × b。多個數就兩兩折疊，總共 O(n log M)，M 是最大值；gcd 一旦變成 1 就可以提前停。

擴展歐幾里得在求 gcd 的同時找出整數 x、y 使 ax + by = gcd(a, b)，這組解一定存在（Bézout 等式）。遞迴寫法：假設已經求出 b·x′ + (a mod b)·y′ = g，把 a mod b = a − ⌊a/b⌋·b 代進去整理，得到 x = y′、y = x′ − ⌊a/b⌋·y′。兩個直接的推論：ax + by = c 有整數解若且唯若 g 整除 c；當 gcd(a, m) = 1 時，ax + my = 1 兩邊取模 m 得到 ax ≡ 1，x 就是 a 的模反元素。Modular Arithmetic 那篇用費馬小定理加快速冪求反元素，但那要求模數是質數；擴展歐幾里得只要求互質。

常見的坑：用減法版 gcd(a − b, b) 代替取餘數，gcd(10⁹, 1) 要減十億次；C++ 的 % 結果跟著被除數的正負號，負數要先取絕對值（C++17 的 std::gcd 已經處理好）；lcm 寫成 a * b / gcd 會在除之前溢位，而且 a、b 有 0 時會除以 0；擴展歐幾里得算出的 x 常是負的，當反元素用之前要 (x % m + m) % m。題目裡看到分數，通常存成約分後的 (分子, 分母) 並把負號固定放在分子，就不會有浮點誤差，也能直接拿來當雜湊表的 key。

03演算法步驟

1. 1先取絕對值。約定 gcd(a, 0) = a，所以 gcd(0, 0) = 0。
2. 2while b != 0：a, b = b, a % b。迴圈結束時 a 就是最大公因數。a < b 也不必先交換，第一輪會自動換過來。
3. 3最小公倍數：任一數為 0 就回傳 0，否則回傳 a // gcd(a, b) * b，先除再乘。多個數就從左到右折疊 gcd 或 lcm。
4. 4擴展版：b == 0 時回傳 (a, 1, 0)；否則遞迴求出 (g, x′, y′)，回傳 (g, y′, x′ − (a // b)·y′)。迭代版則讓每一列維持 r = a·s + b·t，r、s、t 都用「上上列 − q × 上一列」往下算。
5. 5應用：解 ax + by = c 先檢查 c % g == 0，有解時把 x、y 乘上 c / g。求 a 模 m 的反元素時確認 g == 1，答案是 x % m（拉回 0 到 m − 1）。

04互動示範

用 252 和 105，分成兩段。前半段是輾轉相除：左邊逐行寫出「被除數 = 商 × 除數 + 餘數」，黃色是每行的餘數，下一行它就變成除數；右邊的表是餘數序列 r 和商 q。藍色是目前這一步，三次除法後餘數變 0，上一個餘數 21 標成綠色，接著順便算出 lcm = 1260。後半段是擴展歐幾里得：表格多出 s、t 兩欄，每一列都滿足 r = 252·s + 105·t。留意 s、t 和 r 走的是同一條「上上列減掉 q 倍的上一列」規則，最後綠色那一列給出 x = −2、y = 5。

05程式碼

gcd、lcm、擴展歐幾里得，以及用它求模反元素。Python 的擴展版用遞迴寫，和上面「代回去整理係數」的推導一一對應；C++ 用迭代寫，就是示範裡的 r、s、t 表格，而且不佔呼叫堆疊。兩邊最後都示範怎麼對多個數折疊，以及標準庫內建的版本。

from functools import reduce


def gcd(a, b):
    """輾轉相除法：gcd(a, b) = gcd(b, a mod b)。O(log min(a, b))"""
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b                  # 大的換成餘數，直到餘數為 0
    return a


def lcm(a, b):
    """最小公倍數：先除再乘，中間值不會超過答案"""
    if a == 0 or b == 0:
        return 0
    return abs(a // gcd(a, b) * b)


def ext_gcd(a, b):
    """擴展歐幾里得（a, b >= 0）：回傳 (g, x, y)，滿足 a*x + b*y == g"""
    if b == 0:
        return a, 1, 0                   # a*1 + 0*0 == a
    g, x1, y1 = ext_gcd(b, a % b)        # b*x1 + (a % b)*y1 == g
    # 代入 a % b == a - (a // b)*b，整理成 a 和 b 的係數
    return g, y1, x1 - (a // b) * y1


def mod_inverse(a, m):
    """a 在模 m 下的反元素；m 不必是質數，只要 gcd(a, m) == 1"""
    g, x, _ = ext_gcd(a % m, m)
    if g != 1:
        return None                      # 不互質就沒有反元素
    return x % m                         # x 可能是負的，拉回 [0, m)


if __name__ == "__main__":
    print(gcd(48000, 44100))             # 300（44.1 kHz → 48 kHz 的比例是 160/147）
    print(lcm(24, 30))                   # 120
    print(ext_gcd(252, 105))             # (21, -2, 5)：252·(−2) + 105·5 = 21
    print(mod_inverse(17, 3120))         # 2753（RSA 範例的私鑰 d）
    print(mod_inverse(6, 9))             # None（gcd(6, 9) = 3）
    print(reduce(gcd, [84, 126, 210]))   # 42：多個數就兩兩折疊
    print(reduce(lcm, [6, 8, 15]))       # 120
    # 內建：math.gcd，Python 3.9 起還有 math.lcm，兩者都接受多個參數

06練習題

• LeetCode 1979Find Greatest Common Divisor of ArrayEasy
• LeetCode 1071Greatest Common Divisor of Strings（字串版的輾轉相除）Easy
• LeetCode 914X of a Kind in a Deck of Cards（所有出現次數的 gcd）Easy
• LeetCode 592Fraction Addition and Subtraction（通分再約分）Medium
• LeetCode 365Water and Jug Problem（Bézout：gcd 整除目標才量得出來）Medium
• LeetCode 878Nth Magical Number（lcm 加二分答案）Hard