同余与模运算

一句话说明

同余的本质就是“虽然整数本身不同，但除以 m 以后余数一样”，所以在模 m 的世界里它们等价。

最核心的定义

a ≡ b (mod m)

等价于：

m | (a - b)

也就是 a-b 能被 m 整除。

为什么可以边算边取模

因为在模运算下：

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a - b) mod m = ((a mod m) - (b mod m)) mod m
(a * b) mod m = ((a mod m) * (b mod m)) mod m

所以做题时，很多大数完全没必要保留原值，只保留余数就够了。

Go 模板：常用模运算

func AddMod(a, b, mod int) int {
    return (a + b) % mod
}
 
func SubMod(a, b, mod int) int {
    x := (a - b) % mod
    if x < 0 {
        x += mod
    }
    return x
}
 
func MulMod(a, b, mod int) int {
    return (a % mod) * (b % mod) % mod
}

为什么“除法”不能直接做

这是模运算里最容易踩坑的地方。

在模意义下：

a / b

并不是直接除，而是：

a * b^(-1)

也就是说，关键不是“能不能除”，而是：

b 有没有模逆元

逆元什么时候存在

只有当：

gcd(a, m) = 1

时，a 在模 m 下才有逆元。

如果 m 是质数，且 a 不是 m 的倍数，那么逆元一定存在。

Go 模板：质数模数下求逆元

基于费马小定理：

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

func FastPow(a, b, mod int) int {
    result := 1
    a %= mod
    for b > 0 {
        if b&1 == 1 {
            result = result * a % mod
        }
        a = a * a % mod
        b >>= 1
    }
    return result
}
 
func ModInversePrime(a, p int) int {
    return FastPow(a, p-2, p)
}

如果模数不保证是质数，就该转向 扩展欧几里得与模逆元。

最常见的应用场景

• 快速幂取模
• 组合数取模
• 哈希取模
• 线性同余方程
• 防止整数爆炸

易错点

同余与模运算最容易错的地方

• 能加减乘取模，不代表能直接做除法。
• 减法后可能出现负数，要规范回 0..mod-1。
• 看到 % mod 时，最好先确认 mod 是否是质数，因为这会影响逆元求法。

复杂度

操作	复杂度
加减乘取模	O(1)
快速幂	O(log mod)
逆元（费马）	O(log mod)

相关笔记

• 扩展欧几里得与模逆元
• 组合数取模与Lucas定理

---

返回：数学算法