模运算与同余：时钟数学

模运算把无限的整数折叠成有限的环，所有运算都在这个环里封闭完成。

基本性质：运算可以分配进去

模运算的核心性质：(a + b) % m = ((a % m) + (b % m)) % m，乘法同理。这意味着你可以在中间步骤就取模，防止大数溢出。这是快速幂、哈希函数的根本原因。

package main

import "fmt"

// 快速幂：base^exp % mod，O(log exp)
func powMod(base, exp, mod int64) int64 {
    if mod == 1 {
        return 0
    }
    result := int64(1)
    base %= mod
    for exp > 0 {
        if exp&1 == 1 {           // exp 是奇数
            result = result * base % mod
        }
        exp >>= 1
        base = base * base % mod  // 平方
    }
    return result
}

func main() {
    // 2^100 % 1000000007
    fmt.Println(powMod(2, 100, 1_000_000_007))  // 976371285

    // 循环队列：用模运算处理下标
    buf := make([]int, 8)
    head, tail := 0, 0
    enqueue := func(v int) { buf[tail%8] = v; tail++ }
    dequeue := func() int { v := buf[head%8]; head++; return v }
    enqueue(1); enqueue(2); enqueue(3)
    fmt.Println(dequeue(), dequeue())  // 1 2

    // 哈希：字符串哈希用大素数取模防冲突
    hash := func(s string, mod int) int {
        h := 0
        for _, c := range s {
            h = (h*31 + int(c)) % mod
        }
        return h
    }
    fmt.Println(hash("hello", 1_000_003))  // 稳定哈希值
}

同余方程与中国剩余定理

同余 a ≡ b (mod m) 表示 a 和 b 除以 m 的余数相同。中国剩余定理（CRT）告诉我们：如果 m₁, m₂, ... 两两互素，那么联立同余方程组有唯一解。这在密码学（RSA 加速）和日历计算中大量使用。

package main

import "fmt"

// 扩展欧几里得：求 ax + by = gcd(a,b) 的 x,y
func extGCD(a, b int) (g, x, y int) {
    if b == 0 {
        return a, 1, 0
    }
    g, x1, y1 := extGCD(b, a%b)
    return g, y1, x1 - (a/b)*y1
}

// 模逆元：a 在 mod m 下的逆元（需要 gcd(a,m)=1）
func modInverse(a, m int) int {
    _, x, _ := extGCD(a, m)
    return (x%m + m) % m
}

func main() {
    // 3 在 mod 7 下的逆元（3 * x ≡ 1 mod 7）
    inv := modInverse(3, 7)
    fmt.Println(inv, 3*inv%7)  // 5  1 ✓

    // 中国剩余定理：x ≡ 2 mod 3，x ≡ 3 mod 5，x ≡ 2 mod 7 → x = 23
    remainders := []int{2, 3, 2}
    moduli := []int{3, 5, 7}
    M := 3 * 5 * 7  // = 105
    x := 0
    for i, r := range remainders {
        Mi := M / moduli[i]
        x += r * Mi * modInverse(Mi, moduli[i])
    }
    fmt.Println(x % M)  // 23
}

实战：分布式系统的一致性哈希

一致性哈希把节点和键都映射到 [0, 2³²) 的环上（本质是 mod 2³²），键归属于顺时针方向最近的节点。增删节点只影响环上相邻的数据，而不是重新哈希全部数据。这是 Memcached、Cassandra 的核心设计。

模运算是数学的橡皮筋——把无限的数轴弹性地卷成有限的圆环。

— 本课笔记