[algorithms] Math Algorithms 數學演算法

數學演算法是那種「平常用不到，但用到的時候沒學過就完蛋」的知識。GCD 和快速冪幾乎是面試必備，質數篩法和組合數偶爾出現，矩陣快速冪是競賽向。

先講結論

如果你時間有限，優先學 GCD/LCM 和快速冪，這兩個面試考的機率最高。質數篩法次之。排列組合和矩陣快速冪看情況準備。

GCD / LCM：歐幾里得算法

求最大公因數，2300 年前的演算法，到現在還是最優解。

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
 
long lcm(int a, int b) {
    return (long) a / gcd(a, b) * b; // 先除再乘，避免溢位
}

gcd(48, 18):
48 % 18 = 12 → gcd(18, 12)
18 % 12 = 6  → gcd(12, 6)
12 % 6  = 0  → gcd = 6

為什麼 gcd(a, b) == gcd(b, a%b)？因為 a 和 b 的公因數也一定是 a%b 的因數。證明過程可以看數論課本，或者你可以選擇相信歐幾里得。

質數

判斷質數 O(sqrt(n))

boolean isPrime(int n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

為什麼 i += 6？因為所有質數（除了 2 和 3）都是 6k+1 或 6k-1 的形式。跳著檢查可以省掉 2/3 的工作。

埃拉托斯特尼篩法

找 n 以內所有質數。從 2 開始，把它的倍數全部標記掉，剩下的就是質數。

篩 30 以內：
2  3  4  5  6  7  8  9  10...
2  3  ✗  5  ✗  7  ✗  ✗  ✗  ← 篩掉 2 的倍數
2  3     5     7     ✗     ← 篩掉 3 的倍數
2  3     5     7           ← 5² = 25 才開始篩

結果: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

O(n log log n)，接近線性。LeetCode 204「計數質數」就是這題。

快速冪

O(log n) 算 base^exp。原理見 分治法，這裡給完整版（含取模）：

long modPow(long base, long exp, long mod) {
    long result = 1;
    base %= mod;
    while (exp > 0) {
        if ((exp & 1) == 1) result = result * base % mod;
        exp >>= 1;
        base = base * base % mod;
    }
    return result;
}

RSA 加密、大數模運算、費馬小定理求模逆元——都靠快速冪。

排列組合

// C(n, k) = n! / (k! × (n-k)!)
// 用乘除交替的方式避免溢位
long combination(int n, int k) {
    k = Math.min(k, n - k);
    long result = 1;
    for (int i = 0; i < k; i++) {
        result = result * (n - i) / (i + 1);
    }
    return result;
}

帕斯卡三角（DP 求組合數）

         1
        1 1
       1 2 1
      1 3 3 1
     1 4 6 4 1

C(n, k) = C(n-1, k-1) + C(n-1, k)

需要大量組合數的時候，先建帕斯卡三角的表格，查表 O(1)。

矩陣快速冪

把線性遞推加速到 O(log n)。Fibonacci 可以寫成矩陣形式：

[F(n+1)]   [1 1]^n   [F(1)]
[F(n)  ] = [1 0]   × [F(0)]

矩陣乘法 + 快速冪 = O(log n) 求 F(n)。

這招在 n 很大（10^18 之類）的時候才有意義。普通面試不太考，但競賽是常客。

常用公式速查

公式	說明
1+2+…+n = n(n+1)/2	等差數列
(a+b)%m = (a%m+b%m)%m	模加法
(a×b)%m = (a%m×b%m)%m	模乘法
C(n,k) = C(n-1,k-1)+C(n-1,k)	組合遞推

注意模減法要加 m 再取模（避免負數），這是新手常犯的錯。

---

數學演算法就像保險：你希望用不到，但真用到的時候，沒有就很慘。GCD 和快速冪是基本保障，其他的看你要保到什麼程度。