乘法逆元

本文介绍模意义下乘法运算的逆元（Modular Multiplicative Inverse），并介绍如何使用扩展欧几里德算法（Extended Euclidean algorithm）求解乘法逆元。

定义

如果一个线性同余方程 $ax \equiv 1 \pmod b$ ，则称为 $a \bmod b$ 的逆元，记作 $a^{-1}$ 。

如何求逆元

扩展欧几里得法

实现

C++Python

void exgcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}

def exgcd(a, b):
    if b == 0:
        x = 1
        y = 0
        return x, y
    x1, y1 = exgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return x, y

扩展欧几里得法和求解线性同余方程是一个原理，在这里不展开解释。

快速幂法

证明

因为 $ax \equiv 1 \pmod b$ ；

所以 $ax \equiv a^{b-1} \pmod b$ （根据费马小定理）；

所以 $x \equiv a^{b-2} \pmod b$ 。

然后我们就可以用快速幂来求了。

实现

C++Python

int qpow(long long a, int b) {
  int ans = 1;
  a = (a % p + p) % p;
  for (; b; b >>= 1) {
    if (b & 1) ans = (a * ans) % p;
    a = (a * a) % p;
  }
  return ans;
}

def qpow(a, b):
    ans = 1
    a = (a % p + p) % p
    while b:
        if b & 1:
            ans = (a * ans) % p
        a = (a * a) % p
        b >>= 1
    return ans

注意：快速幂法使用了费马小定理，要求是一个素数；而扩展欧几里得法只要求 $\gcd(a, b) = 1$ 。

线性求逆元

求出 $1,2,\dots,n$ 中每个数关于的逆元。

如果对于每个数进行单次求解，以上两种方法就显得慢了，很有可能超时，所以下面来讲一下如何线性（）求逆元。

首先，很显然的 $1^{-1} \equiv 1 \pmod p$ ；

证明

对于 $\forall p \in \mathbf{Z}$ ，有 $1 \times 1 \equiv 1 \pmod p$ 恒成立，故在下的逆元是，而这是推算出其他情况的基础。

其次对于递归情况 $i^{-1}$ ，我们令 $k = \lfloor \frac{p}{i} \rfloor$ ， $j = p \bmod i$ ，有。再放到 $\mod p$ 意义下就会得到： $ki+j \equiv 0 \pmod p$ ；

两边同时乘 $i^{-1} \times j^{-1}$ ：

$kj^{-1}+i^{-1} \equiv 0 \pmod p$

$i^{-1} \equiv -kj^{-1} \pmod p$

再带入 $j = p \bmod i$ ，有，有：

$i^{-1} \equiv -\lfloor\frac{p}{i}\rfloor (p \bmod i)^{-1} \pmod p$

我们注意到 $p \bmod i < i$ ，而在迭代中我们完全可以假设我们已经知道了所有的模下的逆元 $j^{-1}, j < i$ 。

故我们就可以推出逆元，利用递归的形式，而使用迭代实现：

i^{-1} \equiv \begin{cases} 1, & \text{if } i = 1, \\ -\lfloor\frac{p}{i}\rfloor (p \bmod i)^{-1}, & \text{otherwise}. \end{cases} \pmod p

实现

C++Python

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
  inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}

inv[1] = 1
for i in range(2, n + 1):
    inv[i] = (p - p // i) * inv[p % i] % p

使用 $p-\lfloor \dfrac{p}{i} \rfloor$ 来防止出现负数。

另外我们注意到我们没有对 inv[0] 进行定义却可能会使用它：当成立时，我们在代码中会访问 inv[p % i]，也就是 inv[0]，这是因为当时不存在的逆元 $i^{-1}$ 。线性同余方程中指出，如果与不互素时不存在相应的逆元（当一般而言我们会使用一个大素数，比如来确保它有着有效的逆元）。因此需要指出的是：如果没有相应的逆元的时候，inv[i] 的值是未定义的。

另外，根据线性求逆元方法的式子： $i^{-1} \equiv -kj^{-1} \pmod p$

递归求解 $j^{-1}$ , 直到返回。

中间优化可以加入一个记忆化来避免多次递归导致的重复，这样求 $1,2,\dots,n$ 中所有数的逆元的时间复杂度仍是。

注意：如果用以上给出的式子递归进行单个数的逆元求解，目前已知的时间复杂度的上界为 $O(n^{\frac 1 3})$ ，具体请看知乎讨论。算法竞赛中更好地求单个数的逆元的方法有扩展欧几里得法和快速幂法。

线性求任意 n 个数的逆元

上面的方法只能求到的逆元，如果需要求任意给定个数（ $1 \le a_i < p$ ）的逆元，就需要下面的方法：

首先计算个数的前缀积，记为，然后使用快速幂或扩展欧几里得法计算的逆元，记为。

因为是个数的积的逆元，所以当我们把它乘上时，就会和的逆元抵消，于是就得到了到 $a_{n-1}$ 的积逆元，记为 $sv_{n-1}$ 。

同理我们可以依次计算出所有的，于是 $a_i^{-1}$ 就可以用 $s_{i-1} \times sv_i$ 求得。

所以我们就在 $O(n + \log p)$ 的时间内计算出了个数的逆元。

实现

C++Python

s[0] = 1;
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % p;
sv[n] = qpow(s[n], p - 2);
// 当然这里也可以用 exgcd 来求逆元,视个人喜好而定.
for (int i = n; i >= 1; --i) sv[i - 1] = sv[i] * a[i] % p;
for (int i = 1; i <= n; ++i) inv[i] = sv[i] * s[i - 1] % p;

s[0] = 1
for i in range(1, n + 1):
    s[i] = s[i - 1] * a[i] % p
sv[n] = qpow(s[n], p - 2)
# 当然这里也可以用 exgcd 来求逆元,视个人喜好而定.
for i in range(n, 0, -1):
    sv[i - 1] = sv[i] * a[i] % p
for i in range(1, n + 1):
    inv[i] = sv[i] * s[i - 1] % p

逆元练习题

本页面最近更新：2024/5/8 20:33:33，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：iamtwz, abc1763613206, buggg-hfc, dkz051, Enter-tainer, Great-designer, Henry-ZHR, hqztrue, hsfzLZH1, ImpleLee, Ir1d, JellyGoat, jifbt, lhhxxxxx, Marcythm, MegaOwIer, Menci, MioChyan, n-WN, ouuan, PeterlitsZo, Phemon, shawlleyw, Siyuanwww, sshwy, stevebraveman, StudyingFather, thredreams, Tiooo111, Tiphereth-A, WAAutoMaton, Xeonacid, Zhaoyangzhen
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用