Modular Arithmetic模運算

01為什麼需要它

看到這些關鍵字就想到它：答案很大要求取模 10⁹+7、中間計算會溢位、大整數的餘數、要在模數之下做除法（分數、機率、期望值）、次方很大的 a^b mod m、反元素、密碼學與檢查碼。

02核心概念

a mod m 是 a 除以 m 的餘數，a ≡ b (mod m) 表示 a 和 b 除以 m 的餘數相同，也就是 m 整除 a − b。模運算最重要的性質是它能分配到加、減、乘上：(a + b) mod m = ((a mod m) + (b mod m)) mod m，減法和乘法同理。所以每做一次運算就可以立刻取模，中間值永遠小於 m。題目常用的 10⁹+7 是質數，兩個小於它的數相加還在 32 位元有號整數內，相乘不超過 10¹⁸，64 位元整數放得下。

減法和除法要小心。C++ 的 % 會保留被除數的正負號，(3 − 5) % 7 是 −2，要寫成 (a − b + m) % m 拉回 0 到 m − 1；Python 的 % 結果則不會是負數。除法不能分配：(12 / 4) mod 5 = 3，但 12 mod 5 = 2、4 mod 5 = 4，2 除以 4 連整數都不是。解法是反元素：若 b · x ≡ 1 (mod m)，x 就記作 b⁻¹，「除以 b」改成「乘上 b⁻¹」。反元素存在的充要條件是 gcd(b, m) = 1。

模數是質數 p 時，求反元素有現成公式。費馬小定理：a 不是 p 的倍數時 a^(p−1) ≡ 1 (mod p)。證明就是示範裡的觀察：1 到 p − 1 各乘上 a，餘數恰好是 1 到 p − 1 的重新排列，兩邊全部乘起來再約掉 (p−1)! 就得到它。拆出一個 a，a⁻¹ ≡ a^(p−2)，用快速冪 O(log p) 時間、O(1) 空間算出來。模數不是質數時，改用擴展歐幾里得，同樣 O(log m)，前提是 gcd(a, m) = 1。需要 1 到 n 全部的反元素時，遞推式 inv[i] = (p − ⌊p/i⌋) · inv[p mod i] mod p 讓總時間只有 O(n)。

常見的坑：先相乘才取模，int 已經溢位了，乘法前要轉成 64 位元；減法之後忘了加回 m；對合數模數套用費馬小定理，示範裡 5^10 mod 12 得到 1，真正的反元素卻是 5；想求 0 或 p 的倍數的反元素；取模之後還拿來比大小，取模不保留大小順序。另一個容易錯的地方是指數：a^e mod p 的指數可以對 p − 1 取模（前提是 a 不是 p 的倍數），不能對 p 取模。和鄰近課程的關係：Fast Exponentiation 提供 a^e mod m 的計算方法；GCD 的擴展歐幾里得處理非質數模數；下一篇 Combinatorics 要算 C(n, k) mod p，會用反元素把階乘的除法換成乘法。

03演算法步驟

1. 1選定模數 m，每次加、減、乘之後立刻取模，讓中間值永遠小於 m；乘法前確認 (m − 1)² 放得進使用的整數型別。
2. 2減法寫成 (a − b + m) mod m；任何可能是負數的值都用 ((x mod m) + m) mod m 拉回 0 到 m − 1。
3. 3遇到除以 b：先確認 gcd(b, m) = 1，把「除以 b」換成「乘上 b 的反元素」。
4. 4模數是質數 p 時，反元素是 b^(p−2) mod p，用快速冪計算；模數不是質數時用擴展歐幾里得。
5. 5要 1 到 n 全部的反元素時，用 inv[i] = (p − ⌊p/i⌋) · inv[p mod i] mod p 由小到大 O(n) 算完。

04互動示範

在模 13 之下找 5 的反元素。第一段把 k = 1 到 12 逐一乘上 5 再取餘數：藍色是這一步，下排綠色標出已經出現過的餘數，乘到 k = 8 時餘數是 1，黃色標出 5 的反元素 8。乘完 12 個之後每個餘數剛好出現一次，由此推出費馬小定理，得到 5⁻¹ ≡ 5¹¹。第二段用快速冪算 5¹¹ mod 13：11 的二進位是 1011，表格逐位列出 base 和 result，四輪之後 result = 8，和試出來的一致；接著用它算出 7 / 5 ≡ 4。最後換成合數模數 12：a = 4 時餘數只有 0、4、8，1 從來不出現，沒有反元素；a = 5 雖然有反元素 5，照抄費馬公式卻算出 1，黃色框標出這個錯誤。

05程式碼

Python 放快速冪、費馬小定理求反元素、O(n) 算出 1 到 n 的反元素，以及邊讀邊取模的 IBAN 檢查。C++ 放快速冪、費馬版與擴展歐幾里得版的反元素，並示範三個常見情境：機率以分數取模輸出、負數的餘數、指數對 p − 1 取模。

MOD = 1_000_000_007


def mod_pow(a, e, m=MOD):
    """快速冪：a^e mod m，O(log e)。Python 內建的 pow(a, e, m) 做的是同一件事"""
    a %= m
    result = 1 % m
    while e:
        if e & 1:
            result = result * a % m
        a = a * a % m                           # 每一步都取模，數字不會長大
        e >>= 1
    return result


def mod_inv(a, p=MOD):
    """費馬小定理：p 是質數時 a 的反元素是 a^(p-2)。a 是 p 的倍數就沒有反元素"""
    if a % p == 0:
        raise ValueError("a 是 p 的倍數，沒有反元素")
    return mod_pow(a, p - 2, p)


def inverses_upto(n, p=MOD):
    """1 到 n 的反元素一次算完，O(n)。p 必須是大於 n 的質數"""
    inv = [0] * (n + 1)
    if n >= 1:
        inv[1] = 1
    for i in range(2, n + 1):
        inv[i] = (p - p // i) * inv[p % i] % p  # 由 p = (p // i)·i + p % i 取模後整理而來
    return inv


def iban_valid(iban):
    """IBAN 檢查碼：前四碼移到最後、字母換成 10 到 35，整串數字 mod 97 要等於 1。
    這個數字有三十幾位，邊讀邊取模就不用組出大整數"""
    s = iban.replace(" ", "")
    s = s[4:] + s[:4]
    r = 0
    for ch in s:
        v = int(ch, 36)                         # 0-9 → 0 到 9，A-Z → 10 到 35
        r = (r * (100 if v >= 10 else 10) + v) % 97
    return r == 1


if __name__ == "__main__":
    print(mod_pow(5, 11, 13), mod_inv(5, 13))   # 8 8
    print(7 * mod_inv(5, 13) % 13)              # 4：模 13 之下的 7 / 5
    print(mod_inv(2), 2 * mod_inv(2) % MOD)     # 500000004 1
    print(inverses_upto(12, 13)[1:])            # [1, 7, 9, 10, 8, 11, 2, 5, 3, 4, 6, 12]
    print(iban_valid("GB82 WEST 1234 5698 7654 32"), iban_valid("GB82 WEST 1234 5698 7654 23"))   # True False
    print((3 - 5) % 7)                          # 5：Python 的 % 結果永遠不是負數

06練習題

• LeetCode 1497Check If Array Pairs Are Divisible by k（負數的餘數要先拉回正的）Medium
• LeetCode 1015Smallest Integer Divisible by K（只記餘數，不記整個數）Medium
• LeetCode 2550Count Collisions of Monkeys on a Polygon（2ⁿ − 2 取模，減完要加回模數）Medium
• LeetCode 2961Double Modular ExponentiationMedium
• LeetCode 1808Maximize Number of Nice Divisors（拆成 3 的次方，快速冪取模）Hard
• LeetCode 1622Fancy Sequence（全體乘法要反過來做，需要模反元素）Hard