數論完全指南 — GCD、模運算、質數篩法與中國剩餘定理 | 資料結構與演算法

2026/07/16
javascript 資料結構&演算法 數論 Number Theory
數論完全指南 — GCD、模運算、質數篩法與中國剩餘定理 | 資料結構與演算法

數論（Number Theory） 是演算法競賽與技術面試中最常見的數學工具箱，從 歐幾里得演算法（Euclidean Algorithm） 求最大公因數、質數篩法（Sieve of Eratosthenes） 高效列舉質數，到 模運算（Modular Arithmetic） 處理大數取餘、費馬小定理（Fermat’s Little Theorem） 求模反元素，再到 中國剩餘定理（Chinese Remainder Theorem） 合併多模數方程式——這些工具構成了密碼學、雜湊函式、隨機化演算法的底層基石。本文帶你從直覺出發，逐步掌握所有核心數論演算法的原理與完整實作，搭配 JavaScript/TypeScript 與 C++ 雙語言範例，全面解鎖數論演算法的實戰能力。

前言

想像你是一位郵務分揀員，面前有一堆需要投遞的信件。你發現每第 2 封信的收件人在 A 區、每第 3 封在 B 區、每第 5 封在 C 區。有些信件同時符合多個條件——比如第 6 封同時屬於 A 區和 B 區（因為 6 是 2 和 3 的公倍數），第 30 封則三區皆屬。這種「整除」、「倍數」、「餘數」的規律，正是 數論（Number Theory） 的核心研究對象。

在程式設計的世界中，數論無處不在：

  • 密碼學：RSA 加密依賴大質數與模反元素
  • 雜湊函式：模運算將任意大的鍵值映射到固定範圍
  • 競賽與面試：大量題目要求「答案對 10^9 + 7 取餘」
  • 分散式系統：一致性雜湊（Consistent Hashing）使用模運算分配節點

學習本文後，你將能夠：

  • 理解並實作 歐幾里得演算法（GCD） 與 擴展 GCD，求解線性丟番圖方程
  • 掌握 模運算 的基本性質與常見陷阱（負數取模、溢位問題）
  • 使用 Sieve of Eratosthenes 和 線性篩 高效列舉質數
  • 實作 快速冪（Binary Exponentiation） 與 模反元素（Modular Inverse）
  • 理解 費馬小定理 與 中國剩餘定理 的原理與應用
  • 運用數論工具解決 LeetCode 高頻面試題

核心概念

GCD 與 LCM（最大公因數與最小公倍數）

最大公因數（Greatest Common Divisor，GCD） 是能同時整除兩個整數的最大正整數。例如 gcd(48, 18) = 6。

最小公倍數（Least Common Multiple，LCM） 是能同時被兩個整數整除的最小正整數。GCD 和 LCM 之間的關係為：

lcm(a, b) = a × b / gcd(a, b)
          = (a / gcd(a, b)) × b    ← 先除後乘，防溢位

歐幾里得演算法（Euclidean Algorithm）

歐幾里得演算法（又稱 輾轉相除法）是求 GCD 的經典方法，基於以下數學性質：

gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = a

範例：gcd(48, 18)
= gcd(18, 48 % 18) = gcd(18, 12)
= gcd(12, 18 % 12) = gcd(12, 6)
= gcd(6,  12 % 6)  = gcd(6, 0)
= 6

每次取餘至少會讓較大的數減半，因此時間複雜度為 O(log min(a, b))。

模運算（Modular Arithmetic）

模運算是數論的基礎運算，核心性質如下：

(a + b) % m = ((a % m) + (b % m)) % m
(a - b) % m = ((a % m) - (b % m) + m) % m    ← 加 m 防負數
(a × b) % m = ((a % m) × (b % m)) % m
(a / b) % m ≠ (a % m) / (b % m)              ← 除法不能直接取模！

除法在模運算中不能直接操作，需要使用 模反元素（Modular Inverse） 將除法轉換為乘法。

負數取模的陷阱：

在 JavaScript 與 C++ 中，(-7) % 3 = -1，但數學上的正確結果是 2。修正公式為：

((a % m) + m) % m

質數（Prime Numbers）

質數 是大於 1 且只能被 1 和自身整除的正整數。質數在數論中的地位就像化學中的元素——任何大於 1 的正整數都可以唯一分解為質數的乘積（算術基本定理）。

判斷質數的暴力法：試除到 √n
  isPrime(29)：檢查 2, 3, 4, 5 → 都不整除 → 是質數
  isPrime(36)：檢查 2 → 36 % 2 = 0 → 不是質數

為什麼只需要試到 √n？
  若 n = a × b 且 a ≤ b，則 a ≤ √n
  因此若 √n 以內沒有因數，n 就是質數

Sieve of Eratosthenes（埃拉托斯特尼篩法）

當我們需要一次找出某個範圍內的 所有質數 時，逐一判斷太慢。Sieve of Eratosthenes 的思路是：從 2 開始，將每個質數的所有倍數標記為合數。

初始：[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
篩 2：[2, 3, ✗, 5, ✗, 7, ✗, 9,  ✗, 11,  ✗, 13]
篩 3：[2, 3, ✗, 5, ✗, 7, ✗, ✗,  ✗, 11,  ✗, 13]
篩 5：無新標記（25 > 13）
結果：2, 3, 5, 7, 11, 13

優化要點： 對質數 i，從 i * i 開始標記（因為 i * 2、i * 3 … i * (i-1) 已被更小的質數篩過）。

快速冪（Binary Exponentiation）

計算 a^n % m 時，若 n 很大（如 10^18），逐次相乘不可行。快速冪 利用指數的二進位拆分，將 O(n) 降為 O(log n)：

a^13 = a^(1101₂) = a^8 × a^4 × a^1

步驟：
  n=13 (奇數): result *= a → a¹,  a → a²,  n=6
  n=6  (偶數): skip,              a → a⁴,  n=3
  n=3  (奇數): result *= a → a⁵,  a → a⁸,  n=1
  n=1  (奇數): result *= a → a¹³, n=0 → 結束

費馬小定理（Fermat’s Little Theorem）

當 p 為質數且 a 不被 p 整除時：

a^(p-1) ≡ 1 (mod p)

推論：a 的模反元素 a⁻¹ ≡ a^(p-2) (mod p)

這讓我們可以用快速冪在 O(log p) 時間內求出模反元素，前提是模數為質數。

中國剩餘定理（Chinese Remainder Theorem，CRT）

CRT 解決的問題是：給定多個 模數互質 的同餘方程式，求滿足所有方程式的最小正整數 x。

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

M = 3 × 5 × 7 = 105
M₁ = 105/3 = 35,  35⁻¹ ≡ 2 (mod 3),  → 2 × 35 × 2 = 140
M₂ = 105/5 = 21,  21⁻¹ ≡ 1 (mod 5),  → 3 × 21 × 1 = 63
M₃ = 105/7 = 15,  15⁻¹ ≡ 1 (mod 7),  → 2 × 15 × 1 = 30

x = (140 + 63 + 30) % 105 = 233 % 105 = 23

驗證：23 % 3 = 2 ✓, 23 % 5 = 3 ✓, 23 % 7 = 2 ✓

JavaScript / TypeScript 實作

GCD — 迭代與遞迴版本

// ─── GCD（最大公因數）─────────────────────────────────────
// 歐幾里得演算法（輾轉相除法）
// 時間複雜度：O(log min(a, b))

// 迭代版本（推薦，無遞迴堆疊開銷）
function gcd(a: number, b: number): number {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

// 遞迴版本（簡潔但有堆疊深度限制）
function gcdRecursive(a: number, b: number): number {
  if (b === 0) return a;
  return gcdRecursive(b, a % b);
}

// LCM（最小公倍數）— 先除後乘，防止溢位
function lcm(a: number, b: number): number {
  return (a / gcd(a, b)) * b;
}

// ─── 測試 ─────────────────────────────────────────────────
console.log(gcd(48, 18));        // 輸出：6
console.log(gcd(100, 75));       // 輸出：25
console.log(gcd(17, 13));        // 輸出：1（互質）
console.log(lcm(4, 6));          // 輸出：12
console.log(lcm(12, 18));        // 輸出：36

擴展歐幾里得演算法（Extended GCD）

擴展 GCD 不僅求出 gcd(a, b)，還找出整數解 x, y 使得 a*x + b*y = gcd(a, b)。這是求解 線性丟番圖方程（Linear Diophantine Equation） 與計算 模反元素 的核心工具。

// ─── 擴展 GCD ────────────────────────────────────────────
// 回傳 [gcd, x, y]，使得 a*x + b*y = gcd(a, b)
function extendedGcd(a: number, b: number): [number, number, number] {
  if (b === 0) return [a, 1, 0];

  const [g, x1, y1] = extendedGcd(b, a % b);
  // 利用遞推關係：
  // a*x + b*y = g
  // b*x₁ + (a % b)*y₁ = g
  // b*x₁ + (a - ⌊a/b⌋*b)*y₁ = g
  // a*y₁ + b*(x₁ - ⌊a/b⌋*y₁) = g
  const x = y1;
  const y = x1 - Math.floor(a / b) * y1;
  return [g, x, y];
}

// ─── 測試 ─────────────────────────────────────────────────
const [g, x, y] = extendedGcd(35, 15);
console.log(`gcd=${g}, x=${x}, y=${y}`);
// 輸出：gcd=5, x=1, y=-2
// 驗證：35*1 + 15*(-2) = 35 - 30 = 5 ✓

const [g2, x2, y2] = extendedGcd(240, 46);
console.log(`gcd=${g2}, x=${x2}, y=${y2}`);
// 輸出：gcd=2, x=-9, y=47
// 驗證：240*(-9) + 46*47 = -2160 + 2162 = 2 ✓

模運算快速冪（Modular Exponentiation）

// ─── 快速冪（Binary Exponentiation）─────────────────────
// 計算 base^exp % mod
// 時間複雜度：O(log exp)

// BigInt 版本（推薦，適合 mod > 2^26 的場景）
function modPow(base: bigint, exp: bigint, mod: bigint): bigint {
  let result = 1n;
  base %= mod;

  // 確保 base 為正
  if (base < 0n) base += mod;

  while (exp > 0n) {
    // 若指數最低位為 1，將當前 base 乘入結果
    if (exp & 1n) {
      result = (result * base) % mod;
    }
    // base 自乘，指數右移一位（等於除以 2）
    base = (base * base) % mod;
    exp >>= 1n;
  }

  return result;
}

// Number 版本（適合 mod < 2^26 ≈ 6700 萬的小模數場景）
function modPowNum(base: number, exp: number, mod: number): number {
  let result = 1;
  base %= mod;

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

  return result;
}

// ─── 測試 ─────────────────────────────────────────────────
console.log(modPow(2n, 10n, 1000n));
// 輸出：24n（1024 % 1000 = 24）

const MOD = 1_000_000_007n;
console.log(modPow(3n, 100n, MOD));
// 輸出：981453966n

console.log(modPow(2n, 1000000000000000000n, MOD));
// 輸出：49000n（快速冪讓 10^18 次方也能瞬間算完）

Sieve of Eratosthenes（質數篩法）

// ─── Eratosthenes 篩法 ──────────────────────────────────
// 找出 [2, n] 範圍內所有質數
// 時間複雜度：O(N log log N)，空間：O(N)
function sieveOfEratosthenes(n: number): number[] {
  // 使用 Uint8Array 節省記憶體（相比 boolean[]）
  const isPrime = new Uint8Array(n + 1).fill(1);
  isPrime[0] = isPrime[1] = 0;

  // 只需篩到 √n，因為更大的合數已被更小的質因數篩掉
  for (let i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      // 從 i*i 開始標記（i*2, i*3, ..., i*(i-1) 已被更小質數處理）
      for (let j = i * i; j <= n; j += i) {
        isPrime[j] = 0;
      }
    }
  }

  // 收集所有質數
  const primes: number[] = [];
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) primes.push(i);
  }
  return primes;
}

// ─── 測試 ─────────────────────────────────────────────────
console.log(sieveOfEratosthenes(30));
// 輸出：[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

console.log(sieveOfEratosthenes(50).length);
// 輸出：15（50 以內有 15 個質數）

線性篩（Linear Sieve）

線性篩保證每個合數只被其 最小質因數 篩掉一次，時間複雜度嚴格 O(N)。額外的好處是同時求出每個數的最小質因數 minPrime[]，可用於快速質因數分解。

// ─── 線性篩 ─────────────────────────────────────────────
// 時間複雜度：嚴格 O(N)，空間：O(N)
function linearSieve(n: number): {
  primes: number[];
  minPrime: number[];
} {
  const minPrime = new Array(n + 1).fill(0);
  const primes: number[] = [];

  for (let i = 2; i <= n; i++) {
    if (minPrime[i] === 0) {
      // i 是質數，自身即為最小質因數
      minPrime[i] = i;
      primes.push(i);
    }

    // 用已知質數篩掉 i * p 的合數
    for (const p of primes) {
      if (p > minPrime[i] || i * p > n) break;
      minPrime[i * p] = p;
    }
  }

  return { primes, minPrime };
}

// ─── 測試 ─────────────────────────────────────────────────
const { primes, minPrime } = linearSieve(30);
console.log(primes);
// 輸出：[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

console.log(minPrime[12]); // 輸出：2（12 的最小質因數是 2）
console.log(minPrime[15]); // 輸出：3（15 的最小質因數是 3）

質因數分解（Prime Factorization）

// ─── 試除法質因數分解 ───────────────────────────────────
// 時間複雜度：O(√n)
function primeFactorize(n: number): Map<number, number> {
  const factors = new Map<number, number>();

  // 從最小質數開始試除
  for (let d = 2; d * d <= n; d++) {
    while (n % d === 0) {
      factors.set(d, (factors.get(d) || 0) + 1);
      n /= d;
    }
  }

  // 剩餘的 n > 1 本身就是質因數
  if (n > 1) {
    factors.set(n, 1);
  }

  return factors;
}

// ─── 利用線性篩的最小質因數快速分解 ─────────────────────
// 前提：已用 linearSieve 預計算 minPrime[]
// 時間複雜度：O(log n)（每次除以最小質因數）
function factorizeWithMinPrime(
  n: number,
  minPrime: number[]
): Map<number, number> {
  const factors = new Map<number, number>();

  while (n > 1) {
    const p = minPrime[n];
    let count = 0;
    while (n % p === 0) {
      n /= p;
      count++;
    }
    factors.set(p, count);
  }

  return factors;
}

// ─── 測試 ─────────────────────────────────────────────────
console.log(primeFactorize(360));
// 輸出：Map { 2 => 3, 3 => 2, 5 => 1 }（360 = 2³ × 3² × 5）

console.log(primeFactorize(97));
// 輸出：Map { 97 => 1 }（97 是質數）

// 使用線性篩版本
const { minPrime: mp } = linearSieve(1000);
console.log(factorizeWithMinPrime(360, mp));
// 輸出：Map { 2 => 3, 3 => 2, 5 => 1 }

模反元素（Modular Inverse）

// ─── 模反元素 ───────────────────────────────────────────
// a 的模反元素 a⁻¹ 滿足：a × a⁻¹ ≡ 1 (mod m)
// 應用：計算 (a / b) % m → a * inv(b) % m

// 方法一：費馬小定理（m 必須為質數）
// a⁻¹ ≡ a^(m-2) (mod m)，時間：O(log m)
function modInverseFermat(a: bigint, m: bigint): bigint {
  return modPow(a, m - 2n, m);
}

// 方法二：擴展 GCD（適用任意模數，只要 gcd(a, m) = 1）
function modInverseExtGcd(a: number, m: number): number {
  const [g, x] = extendedGcd(a, m);
  if (g !== 1) {
    throw new Error(`模反元素不存在：gcd(${a}, ${m}) = ${g} ≠ 1`);
  }
  return ((x % m) + m) % m;
}

// 方法三：線性預計算 [1, n] 所有逆元（O(N)）
// 適合需要大量逆元的場景（如組合數計算）
function precomputeInverses(n: number, mod: number): number[] {
  const inv = new Array(n + 1).fill(0);
  inv[1] = 1;

  for (let i = 2; i <= n; i++) {
    // 推導式：inv[i] = -(mod / i) * inv[mod % i] % mod
    inv[i] =
      ((-(Math.floor(mod / i)) * inv[mod % i]) % mod + mod) % mod;
  }

  return inv;
}

// ─── 測試 ─────────────────────────────────────────────────
const MOD_P = 1_000_000_007n;
const inv3 = modInverseFermat(3n, MOD_P);
console.log(inv3);
// 輸出：333333336n

// 驗證：3 × 333333336 % (10^9+7) = 1
console.log((3n * inv3) % MOD_P);
// 輸出：1n ✓

console.log(modInverseExtGcd(3, 7));
// 輸出：5（因為 3 × 5 = 15 ≡ 1 (mod 7)）

const invTable = precomputeInverses(10, 13);
console.log(invTable.slice(1, 11));
// 輸出：[1, 7, 9, 10, 8, 11, 2, 5, 3, 4]
// 驗證：2 × 7 = 14 ≡ 1 (mod 13) ✓

中國剩餘定理（CRT）

// ─── 中國剩餘定理 ───────────────────────────────────────
// 解聯立同餘方程式：
//   x ≡ r₁ (mod m₁)
//   x ≡ r₂ (mod m₂)
//   ...
//   x ≡ rₖ (mod mₖ)
// 前提：所有 mᵢ 兩兩互質
// 回傳最小非負整數解 x

function chineseRemainderTheorem(
  remainders: bigint[],
  moduli: bigint[]
): bigint {
  const n = remainders.length;

  // 計算所有模數的乘積 M
  let M = 1n;
  for (const m of moduli) {
    M *= m;
  }

  let result = 0n;

  for (let i = 0; i < n; i++) {
    const Mi = M / moduli[i]; // Mi = M / mᵢ
    // 求 Mi 在 mod mᵢ 下的逆元
    const MiInv = modPow(Mi, moduli[i] - 2n, moduli[i]);

    // 累加 rᵢ × Mi × Mi⁻¹
    result = (result + remainders[i] * Mi % M * MiInv) % M;
  }

  return (result + M) % M; // 確保結果為正
}

// ─── 擴展 GCD 版本（適用非質數模數）────────────────────
function extGcdBigInt(
  a: bigint,
  b: bigint
): [bigint, bigint, bigint] {
  if (b === 0n) return [a, 1n, 0n];
  const [g, x1, y1] = extGcdBigInt(b, a % b);
  return [g, y1, x1 - (a / b) * y1];
}

function crtGeneral(
  remainders: bigint[],
  moduli: bigint[]
): bigint {
  let r = remainders[0];
  let m = moduli[0];

  for (let i = 1; i < remainders.length; i++) {
    const r2 = remainders[i];
    const m2 = moduli[i];
    const [g, p, _q] = extGcdBigInt(m, m2);

    if ((r2 - r) % g !== 0n) {
      throw new Error("無解：模數不互質且餘數不相容");
    }

    const lcmVal = (m / g) * m2;
    r = (r + m * ((r2 - r) / g % (m2 / g) * p % (m2 / g))) % lcmVal;
    r = (r + lcmVal) % lcmVal;
    m = lcmVal;
  }

  return r;
}

// ─── 測試 ─────────────────────────────────────────────────
// x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
const answer = chineseRemainderTheorem(
  [2n, 3n, 2n],
  [3n, 5n, 7n]
);
console.log(answer);
// 輸出：23n

// 驗證
console.log(23n % 3n); // 輸出：2n ✓
console.log(23n % 5n); // 輸出：3n ✓
console.log(23n % 7n); // 輸出：2n ✓

C++ 對照實作

以下提供與 TypeScript 版本對應的 C++ 實作。C++ 在數論計算中有幾個顯著差異：

  • 原生 64 位整數：long long（64-bit）直接可用，不需要 BigInt
  • __int128 防溢位：當兩個接近 10^18 的數相乘時，中間結果可能超過 64 位，C++ 提供 __int128 處理
  • 內建函式：C++17 提供 std::gcd 和 std::lcm（需 <numeric>），GCC 提供 __gcd
  • 位元運算效能：C++ 的位元運算比 JavaScript 更直接，不需考慮 32-bit 截斷
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// ─── GCD / LCM ─────────────────────────────────────────
ll gcd(ll a, ll b) {
    while (b) { a %= b; swap(a, b); }
    return a;
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b; // 先除後乘防溢位
}

// ─── 擴展 GCD ──────────────────────────────────────────
ll extGcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll g = extGcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// ─── 快速冪 ────────────────────────────────────────────
ll modPow(ll base, ll exp, ll mod) {
    ll result = 1;
    base %= mod;
    if (base < 0) base += mod;

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

// ─── 模反元素 ──────────────────────────────────────────
// 費馬小定理法（mod 必須為質數）
ll modInverse(ll a, ll mod) {
    return modPow(a, mod - 2, mod);
}

// 擴展 GCD 法（適用任意互質模數）
ll modInverseExtGcd(ll a, ll m) {
    ll x, y;
    ll g = extGcd(a, m, x, y);
    if (g != 1) return -1; // 逆元不存在
    return (x % m + m) % m;
}

// ─── Sieve of Eratosthenes ─────────────────────────────
vector<int> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; (ll)i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    vector<int> primes;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) primes.push_back(i);
    }
    return primes;
}

// ─── 線性篩 ────────────────────────────────────────────
void linearSieve(int n, vector<int>& primes,
                 vector<int>& minPrime) {
    minPrime.assign(n + 1, 0);

    for (int i = 2; i <= n; i++) {
        if (minPrime[i] == 0) {
            minPrime[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > minPrime[i] || (ll)i * p > n) break;
            minPrime[i * p] = p;
        }
    }
}

// ─── 質因數分解 ────────────────────────────────────────
map<int, int> primeFactorize(int n) {
    map<int, int> factors;
    for (int d = 2; (ll)d * d <= n; d++) {
        while (n % d == 0) {
            factors[d]++;
            n /= d;
        }
    }
    if (n > 1) factors[n]++;
    return factors;
}

// ─── 中國剩餘定理 ──────────────────────────────────────
ll chineseRemainderTheorem(vector<ll>& remainders,
                           vector<ll>& moduli) {
    int n = remainders.size();
    ll M = 1;
    for (ll m : moduli) M *= m;

    ll result = 0;
    for (int i = 0; i < n; i++) {
        ll Mi = M / moduli[i];
        ll MiInv = modInverse(Mi % moduli[i], moduli[i]);
        result = (result +
            (__int128)remainders[i] * Mi % M * MiInv) % M;
    }

    return (result + M) % M;
}

// ─── 測試 ───────────────────────────────────────────────
int main() {
    // GCD / LCM
    cout << "gcd(48, 18) = " << gcd(48, 18) << endl; // 6
    cout << "lcm(4, 6) = " << lcm(4, 6) << endl;     // 12

    // 擴展 GCD
    ll x, y;
    ll g = extGcd(35, 15, x, y);
    cout << "extGcd(35,15): g=" << g
         << " x=" << x << " y=" << y << endl;
    // g=5, x=1, y=-2

    // 快速冪
    const ll MOD = 1e9 + 7;
    cout << "2^10 % 1000 = " << modPow(2, 10, 1000) << endl;
    // 24

    // 質數篩
    auto primes = sieveOfEratosthenes(30);
    for (int p : primes) cout << p << " ";
    cout << endl;
    // 2 3 5 7 11 13 17 19 23 29

    // 質因數分解
    auto factors = primeFactorize(360);
    for (auto& [p, e] : factors) {
        cout << p << "^" << e << " ";
    }
    cout << endl;
    // 2^3 3^2 5^1

    // CRT
    vector<ll> r = {2, 3, 2}, m = {3, 5, 7};
    cout << "CRT answer = "
         << chineseRemainderTheorem(r, m) << endl;
    // 23

    return 0;
}

C++ vs TypeScript 實作差異整理：

面向TypeScriptC++
大整數BigInt（1000000007n）long long + __int128
GCD 內建無（需自行實作）std::gcd（C++17）
溢位處理BigInt 無上限__int128 中間結果
陣列初始化new Array(n).fill(0)vector<int>(n, 0)
位元運算注意 32-bit 截斷原生 64-bit 支援
效能較慢（適合練習）較快（適合競賽）

複雜度分析

演算法時間複雜度空間複雜度備註
歐幾里得 GCDO(log min(a, b))O(1)迭代版本
擴展 GCDO(log min(a, b))O(log min(a, b))遞迴堆疊
快速冪O(log n)O(1)迭代版本
判斷質數（試除法）O(√n)O(1)—
Sieve of EratosthenesO(N log log N)O(N)接近線性
線性篩O(N)O(N)嚴格線性，額外記錄 minPrime
質因數分解（試除法）O(√n)O(log n)因數個數最多 O(log n)
質因數分解（minPrime）O(log n)O(1)需 O(N) 預處理
模反元素（費馬小定理）O(log p)O(1)p 必須為質數
模反元素（擴展 GCD）O(log m)O(log m)適用任意互質模數
線性逆元預計算O(N)O(N)預計算 [1, N] 所有逆元
中國剩餘定理O(k log M)O(k)k 為方程式數量
Miller-Rabin 素性測試O(k log² n)O(1)k 為測試輪數

變體與延伸

Miller-Rabin 素性測試

當數字非常大（超過 10^18）時，Sieve 無法使用。Miller-Rabin 是一種機率型素性測試，使用多個基底可以達到確定性結果（對有限範圍的整數）。

// ─── Miller-Rabin 素性測試 ──────────────────────────────
function millerRabin(n: bigint, a: bigint): boolean {
  if (n % a === 0n) return n === a;

  // 將 n-1 分解為 d × 2^r
  let d = n - 1n;
  let r = 0n;
  while (d % 2n === 0n) {
    d /= 2n;
    r++;
  }

  // 計算 a^d mod n
  let x = modPow(a, d, n);
  if (x === 1n || x === n - 1n) return true;

  // 反覆平方 r-1 次
  for (let i = 0n; i < r - 1n; i++) {
    x = (x * x) % n;
    if (x === n - 1n) return true;
  }

  return false;
}

// 確定性版本：對 n < 3.3 × 10^24 範圍正確
function isPrime(n: bigint): boolean {
  if (n < 2n) return false;
  if (n < 4n) return true;
  if (n % 2n === 0n) return false;

  const witnesses = [2n, 3n, 5n, 7n, 11n, 13n,
                     17n, 19n, 23n, 29n, 31n, 37n];

  for (const a of witnesses) {
    if (n === a) return true;
    if (!millerRabin(n, a)) return false;
  }
  return true;
}

// ─── 測試 ─────────────────────────────────────────────────
console.log(isPrime(1000000007n)); // 輸出：true（常用模數）
console.log(isPrime(998244353n));  // 輸出：true（NTT 常用模數）
console.log(isPrime(100n));        // 輸出：false
console.log(isPrime(2n));          // 輸出：true

歐拉函數（Euler’s Totient Function）

歐拉函數 phi(n) 計算 [1, n] 中與 n 互質的正整數個數。它是費馬小定理的推廣——歐拉定理：若 gcd(a, n) = 1，則 a^phi(n) ≡ 1 (mod n)。

// ─── 歐拉函數 ──────────────────────────────────────────
// 公式：phi(n) = n × ∏(1 - 1/p)，p 為 n 的所有質因數
function eulerTotient(n: number): number {
  let result = n;

  for (let p = 2; p * p <= n; p++) {
    if (n % p === 0) {
      // 移除所有 p 因子
      while (n % p === 0) n /= p;
      result -= result / p; // result *= (1 - 1/p)
    }
  }

  if (n > 1) {
    result -= result / n; // 最後剩下的質因數
  }

  return result;
}

// 篩法批量計算 [1, n] 所有 phi 值
function sieveTotient(n: number): number[] {
  const phi = new Array(n + 1).fill(0);
  for (let i = 0; i <= n; i++) phi[i] = i;

  for (let i = 2; i <= n; i++) {
    if (phi[i] === i) {
      // i 是質數
      for (let j = i; j <= n; j += i) {
        phi[j] -= phi[j] / i; // phi[j] *= (1 - 1/i)
      }
    }
  }

  return phi;
}

// ─── 測試 ─────────────────────────────────────────────────
console.log(eulerTotient(12));
// 輸出：4（與 12 互質的數：1, 5, 7, 11）

console.log(eulerTotient(7));
// 輸出：6（質數 p 的 phi(p) = p-1）

console.log(sieveTotient(12));
// 輸出：[0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4]

Mobius 函數（進階）

Mobius 函數 mu(n) 在容斥原理與數論反演（Mobius Inversion）中扮演核心角色：

mu(1) = 1
mu(n) = 0     若 n 有平方因子（如 4, 8, 12, ...）
mu(n) = (-1)^k 若 n 是 k 個不同質數的乘積

// ─── Mobius 函數（篩法計算）─────────────────────────────
function sieveMobius(n: number): number[] {
  const mu = new Array(n + 1).fill(0);
  const minPrimeArr = new Array(n + 1).fill(0);
  const primesArr: number[] = [];

  mu[1] = 1;

  for (let i = 2; i <= n; i++) {
    if (minPrimeArr[i] === 0) {
      minPrimeArr[i] = i;
      primesArr.push(i);
      mu[i] = -1; // 質數的 mu = -1
    }
    for (const p of primesArr) {
      if (p > minPrimeArr[i] || i * p > n) break;
      minPrimeArr[i * p] = p;

      if (i % p === 0) {
        mu[i * p] = 0; // 有平方因子
      } else {
        mu[i * p] = -mu[i]; // 多一個質因數，翻轉符號
      }
    }
  }

  return mu;
}

// ─── 測試 ─────────────────────────────────────────────────
const mu = sieveMobius(12);
console.log(mu);
// 輸出：[0, 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0]
// mu(1)=1, mu(2)=-1, mu(6)=1(=2×3, 兩個質因數)
// mu(4)=0(4=2², 有平方因子)

常見面試考點

數論在面試中的出題頻率很高，以下整理常見考點與應對策略：

1. GCD / LCM 相關

  • 求兩數或多數的 GCD/LCM
  • 判斷兩數是否互質（gcd = 1）
  • 利用 GCD 簡化分數
  • 關鍵公式：lcm(a, b) = a / gcd(a, b) * b（先除後乘防溢位）

2. 模運算相關

  • 計算大數模運算（避免溢位）
  • 負數取模的正確處理：((a % m) + m) % m
  • 「答案對 10^9 + 7 取餘」的題目套路：加減乘直接取模，除法用模反元素

3. 質數相關

  • 判斷質數（試除法，O(√n)）
  • 計算範圍內質數個數（Sieve）
  • 質因數分解
  • 唯一分解定理的應用

4. 快速冪相關

  • 實作 pow(x, n)（包含負指數處理）
  • 矩陣快速冪（斐波那契數列加速）
  • 超大指數取模（a^b % m，b 可能是陣列表示的超大數）

5. 組合數學（常搭配數論出題）

  • C(n, k) % p 的計算（階乘 + 逆元預計算）
  • Catalan 數
  • 容斥原理

LeetCode 練習

以下精選 5 道與數論密切相關的 LeetCode 題目，涵蓋從基礎到進階的各個面向：

204. Count Primes（計算質數數量）

難度： Medium | 方法： Sieve of Eratosthenes

給定整數 n，回傳小於 n 的質數個數。

function countPrimes(n: number): number {
  if (n < 2) return 0;

  // 使用 Uint8Array 節省記憶體
  const isPrime = new Uint8Array(n).fill(1);
  isPrime[0] = isPrime[1] = 0;

  for (let i = 2; i * i < n; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j < n; j += i) {
        isPrime[j] = 0;
      }
    }
  }

  let count = 0;
  for (let i = 2; i < n; i++) {
    if (isPrime[i]) count++;
  }
  return count;
}

// 測試
console.log(countPrimes(10));  // 輸出：4（2, 3, 5, 7）
console.log(countPrimes(0));   // 輸出：0
console.log(countPrimes(1));   // 輸出：0
console.log(countPrimes(100)); // 輸出：25

複雜度： 時間 O(N log log N)，空間 O(N)

50. Pow(x, n)（快速冪）

難度： Medium | 方法： Binary Exponentiation

function myPow(x: number, n: number): number {
  // 處理負指數：x^(-n) = (1/x)^n
  if (n < 0) {
    x = 1 / x;
    n = -n;
  }

  let result = 1;
  let base = x;

  while (n > 0) {
    if (n & 1) result *= base; // 奇數指數：乘入結果
    base *= base;              // base 自乘
    n >>= 1;                   // 指數減半
  }

  return result;
}

// 測試
console.log(myPow(2.0, 10));   // 輸出：1024.0
console.log(myPow(2.1, 3));    // 輸出：9.261
console.log(myPow(2.0, -2));   // 輸出：0.25

複雜度： 時間 O(log n)，空間 O(1)

878. Nth Magical Number（第 N 個神奇數字）

難度： Hard | 方法： 二分搜尋 + GCD/LCM + 容斥原理

若正整數能被 a 或 b 整除，則稱為「神奇數字」。給定 n, a, b，求第 n 個神奇數字（mod 10^9+7）。

function nthMagicalNumber(n: number, a: number, b: number): number {
  const MOD = 1_000_000_007n;

  function gcdLocal(x: number, y: number): number {
    while (y) { [x, y] = [y, x % y]; }
    return x;
  }

  const lcmAB = (a / gcdLocal(a, b)) * b;

  // count(x)：不超過 x 的神奇數字數量（容斥原理）
  function count(x: number): number {
    return Math.floor(x / a) + Math.floor(x / b)
         - Math.floor(x / lcmAB);
  }

  // 二分搜尋：找最小 x 使得 count(x) >= n
  let lo = Math.min(a, b);
  let hi = Math.min(a, b) * n;

  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (count(mid) >= n) hi = mid;
    else lo = mid + 1;
  }

  return Number(BigInt(lo) % MOD);
}

// 測試
console.log(nthMagicalNumber(1, 2, 3));  // 輸出：2
console.log(nthMagicalNumber(4, 2, 3));  // 輸出：6
console.log(nthMagicalNumber(5, 2, 4));  // 輸出：10

複雜度： 時間 O(log(N x min(a, b)))，空間 O(1)

372. Super Pow（超級次方）

難度： Medium | 方法： 快速冪 + 遞歸分解大指數

計算 a^b mod 1337，其中 b 是以陣列形式表示的超大正整數。

function superPow(a: number, b: number[]): number {
  const MOD = 1337;

  // 快速冪（小模數，用 Number 即可）
  function power(base: number, exp: number): number {
    let result = 1;
    base %= MOD;
    while (exp > 0) {
      if (exp & 1) result = (result * base) % MOD;
      base = (base * base) % MOD;
      exp >>= 1;
    }
    return result;
  }

  // 核心遞歸：a^[1,5,6,4] = (a^[1,5,6])^10 × a^4
  function solve(idx: number): number {
    if (idx < 0) return 1;

    // 前面部分的結果取 10 次方，再乘上當前位的貢獻
    return (power(solve(idx - 1), 10) * power(a, b[idx])) % MOD;
  }

  return solve(b.length - 1);
}

// 測試
console.log(superPow(2, [3]));         // 輸出：8（2^3 = 8）
console.log(superPow(2, [1, 0]));      // 輸出：1024 % 1337 = 1024
console.log(superPow(2, [1, 0, 0]));   // 輸出：2^100 % 1337 = 1169

複雜度： 時間 O(k log 10)，其中 k 為指數陣列長度，空間 O(k)

1819. Number of Different Subsequences GCDs

難度： Hard | 方法： GCD + 枚舉因數

給定一個正整數陣列 nums，找出所有不同子序列的 GCD 的不同值個數。

function countDifferentSubsequenceGCDs(nums: number[]): number {
  // 核心思路：枚舉每個可能的 GCD 值 g（從 1 到 max(nums)）
  // 對每個 g，檢查是否存在一個子序列的 GCD 恰好為 g
  // 等價於：在 nums 中找出所有 g 的倍數，計算它們的 GCD
  //         如果結果恰好為 g，則 g 是一個可行的子序列 GCD

  const maxVal = Math.max(...nums);
  const exists = new Uint8Array(maxVal + 1);
  for (const x of nums) exists[x] = 1;

  let count = 0;

  for (let g = 1; g <= maxVal; g++) {
    let currentGcd = 0;

    // 枚舉 g 的所有倍數
    for (let multiple = g; multiple <= maxVal; multiple += g) {
      if (exists[multiple]) {
        currentGcd = gcd(currentGcd, multiple);

        // 提前終止：GCD 已經等於 g，不可能更小
        if (currentGcd === g) break;
      }
    }

    if (currentGcd === g) count++;
  }

  return count;
}

// 測試
console.log(countDifferentSubsequenceGCDs([6, 10, 3]));
// 輸出：5（可能的 GCD：1, 2, 3, 6, 10）

console.log(countDifferentSubsequenceGCDs([5, 15, 40, 5, 6]));
// 輸出：7

複雜度： 時間 O(M log M)（M 為最大值，調和級數），空間 O(M)

總結

本文從最基礎的 歐幾里得演算法 出發，系統性地介紹了數論中最重要的演算法工具：

  1. GCD / LCM：輾轉相除法與擴展 GCD，處理整除性問題與線性丟番圖方程
  2. 模運算：加減乘的模運算性質、負數取模修正、模反元素的三種求法
  3. 質數篩法：Eratosthenes 篩與線性篩，高效列舉質數與質因數分解
  4. 快速冪：O(log n) 計算大數次方，搭配模運算處理溢位
  5. 費馬小定理：質數模下的模反元素速算
  6. 中國剩餘定理：合併多模數同餘方程式
  7. 進階主題：Miller-Rabin 素性測試、歐拉函數、Mobius 函數

這些工具不僅是演算法競賽的標配，更是密碼學、分散式系統、資料結構設計的底層基石。掌握數論思維，能讓你在面對「答案對 10^9+7 取餘」這類題目時游刃有餘。

在下一篇文章中，我們將進入 計算幾何（Computational Geometry） 的世界，探索向量運算、凸包演算法、線段交點判斷等幾何演算法的核心技術。

上一篇：032 — 字串演算法
BenZ Software Developer

熱愛技術的軟體開發者，在這裡分享程式開發經驗與學習筆記。