模逆元计算

模运算中的除法

我们已经学习了模加法、减法和乘法。它们都有一个很好的性质，就是可以先把数字取模再进行运算，这能有效防止结果溢出。比如：

$(a * b) \% p = ((a \% p) * (b \% p)) \% p$

但除法却不一样。 $(a / b) \% p$ 并不等于 $((a \% p) / (b \% p)) \% p$ 。举个简单的例子， $(100 / 50) \% 20 = 2 \% 20 = 2$ 。但如果先取模， $(100 \% 20) / (50 \% 20) = 0 / 10 = 0$ 。结果完全不同。

那么，在模运算的世界里，我们该如何处理除法呢？答案是把它变成乘法。

在模运算中，除以一个数，等价于乘以这个数的“模逆元”。

这个听起来有点陌生的“模逆元”到底是什么？

什么是模逆元

逆元

noun

在模 p 的意义下，如果整数 a 和 x 满足 a * x ≡ 1 (mod p)，那么我们称 x 是 a 关于模 p 的乘法逆元。通常记作 a⁻¹。

这个定义可能有点抽象。我们可以把它和倒数的概念类比一下。在普通算术里，一个数 a 的倒数是 $1/a$ ，因为 $a * (1/a) = 1$ 。在模运算里，a 的逆元 x 扮演了类似的角色，只不过满足的条件是 $(a * x) \% p = 1$ 。

举个例子，我们想找 3 关于模 7 的逆元。我们需要找到一个整数 x，使得 $(3 * x) \% 7 = 1$ 。我们可以试一下：

$3 * 1 \% 7 = 3$
$3 * 2 \% 7 = 6$
$3 * 3 \% 7 = 9 \% 7 = 2$
$3 * 4 \% 7 = 12 \% 7 = 5$
$3 * 5 \% 7 = 15 \% 7 = 1$

找到了！当 x=5 时，等式成立。所以，5 就是 3 关于模 7 的逆元。

有了逆元，我们就能把除法转换成乘法了。

(a / b) \pmod p = (a \cdot b^{-1}) \pmod p

但是，一个一个去试太慢了。我们需要一种更高效的方法来计算逆元。这时，我们在上一章学过的费马小定理就派上用场了。

用快速幂求逆元

让我们回顾一下费马小定理：如果 p 是一个质数，且整数 a 不是 p 的倍数，那么有：

a^{p-1} \equiv 1 \pmod p

我们可以对这个公式做一点小小的变形，把它拆成两部分：

a \cdot a^{p-2} \equiv 1 \pmod p

现在，对比一下逆元的定义： $a \cdot x \equiv 1 \pmod p$ 。

你会发现， $a^{p-2}$ 恰好就扮演了逆元 x 的角色！

这意味着，当 p 是质数时，a 关于模 p 的逆元就是 $a^{p-2}$ 。而计算 $a^{p-2} \% p$ 正是我们上一章学习的快速幂算法的拿手好戏。

当模数 p 是质数时，b 的逆元就是 $b^{p-2} \% p$ 。

所以，计算 $(a / b) \% p$ 的完整流程就清晰了：

计算 b 的逆元，即用快速幂计算 $b^{p-2} \% p$ 。
将除法转化为乘法，计算 $(a * (b^{p-2})) \% p$ 。

下面是一个 C++ 函数，它结合了快速幂来计算逆元。

// 引入 long long 是为了防止中间计算溢出
typedef long long ll;

// 快速幂函数 (来自上一章)
ll power(ll base, ll exp, ll mod) {
    ll res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

// 计算 b 在模 p 下的乘法逆元
// 要求 p 是一个质数
ll modInverse(ll b, ll p) {
    return power(b, p - 2, p);
}

// 示例：计算 (a / b) % p
ll modDivide(ll a, ll b, ll p) {
    ll inv_b = modInverse(b, p); // 计算 b 的逆元
    return (a * inv_b) % p;      // 转换为乘法
}

这种方法在计算组合数取模时特别有用，例如计算 $C(n, k) \% p = (n! / (k! * (n-k)!)) \% p$ 。我们可以预先计算阶乘，然后用模逆元来处理除法。

逆元存在的条件

需要注意的是，模逆元不是一定存在的。一个数 a 关于模 p 的逆元存在的充分必要条件是 a 和 p 互质，即它们的最大公约数 gcd(a, p) = 1。

当我们使用费马小定理来求逆元时，我们已经隐含地满足了这个条件。因为费马小定理要求模数 p 是一个质数，而 a 不是 p 的倍数。如果 p 是质数，那么唯一能和它不互质的数就是它自己的倍数。所以，只要 a 不是 p 的倍数，gcd(a, p) 就一定是 1，逆元就一定存在。

如果 p 不是质数，或者 a 是 p 的倍数，就不能使用这种方法了。比如，4 关于模 6 的逆元就不存在，因为你找不到任何整数 x 使得 $(4 * x) \% 6 = 1$ 。

Quiz Questions 1/7

为什么在模运算中，我们不能像处理加法、减法和乘法一样直接进行除法运算，即 (a / b) % p 通常不等于 ((a % p) / (b % p)) % p？

Quiz Questions 2/7

整数 x 是整数 a 关于模 p 的乘法逆元的定义是什么？

现在你已经掌握了将模除法转化为模乘法的关键技巧。这是解决许多编程竞赛中数论问题的基础。

从零开始掌握模运算算法