前言

在演算法與系統設計面試中，最大公因數（GCD） 與 最小公倍數（LCM） 是基礎數學問題，卻有非常多延伸應用。
除了常見的數論題外，GCD/LCM 也經常出現在 排程問題、分散式系統設計、加密演算法 中。

核心概念

最大公因數（Greatest Common Divisor，GCD），指某幾個整數共有因數中最大的一個。

定義： 能同時整除 a 與 b 的最大整數。

數學公式：

\gcd(a, b) = \gcd(b, a \bmod b)

方法：

實作方式：

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

TIP

Python 可以直接用函式庫 from math import lcm

最小公倍數是數論中的一個概念。若一個數 x 能被另外兩個數 a, b 整除，且 x >= a, b 則 x 為 a 和 b 的公倍數。 a 和 b 的公倍數可以有無數個，其中最小的稱之為最小公倍數。

定義： 能同時被 a 與 b 整除的最小正整數。

數學公式：

\text{lcm}(a, b) = \frac{|a \times b|}{\gcd(a, b)}

實作方式：

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

IMPORTANT

乘法可能造成整數溢位（overflow），實作時常用先除後乘： a / gcd(a,b) * b（注意順序與正負號）。若數字可能為負數，需加上絕對值。

TIP

Python 可以直接用函式庫 from math import lcm

題目：給定一個整數陣列，找出所有數字的 GCD。

from math import gcd
from functools import reduce

def array_gcd(nums):
    return reduce(gcd, nums)

題目：判斷能否用兩個水壺量出 target 升水。核心：若 target % gcd(x, y) == 0，則可解。

from math import gcd

def can_measure_water(x, y, target):
    return target == 0 or (x + y >= target and target % gcd(x, y) == 0)

若機器 A 每 a 秒執行一次，機器 B 每 b 秒執行一次，那麼兩者同時執行的時間點為 LCM(a, b)。