乘法逆元

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

逆元简介¶

如果一个线性同余方程，则称为的逆元，记作。

如何求逆元¶

扩展欧几里得法¶

模板代码

// C++ Version
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;
}

# Python Version
def exgcd(a, b, x, y):
  if b == 0:
      x, y = 1, 0
      return
  exgcd(b, a % b, y, x)
  y = y - (a // b * x)

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

快速幂法¶

因为；

所以（根据费马小定理）；

所以。

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

模板代码

// C++ Version
inline 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;
}

# Python Version
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

注意使用费马小定理需要限制是一个素数，而扩展欧几里得算法只要求。

线性求逆元¶

求出中每个数关于的逆元。

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

首先，很显然的；

证明

对于，有恒成立，故在下的逆元是，而这是推算出其他情况的基础。

其次对于递归情况，我们令，，有。再放到意义下就会得到：；

两边同时乘：

再带入，有，有：

我们注意到，而在迭代中我们完全可以假设我们已经知道了所有的模下的逆元。

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

代码实现

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

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

使用来防止出现负数。

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

另外，根据线性求逆元方法的式子：

递归求解 , 直到返回。

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

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

线性求任意 n 个数的逆元¶

上面的方法只能求到的逆元，如果需要求任意给定个数（）的逆元，就需要下面的方法：

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

因为是个数的积的逆元，所以当我们把它乘上时，就会和的逆元抵消，于是就得到了到的积逆元，记为。

同理我们可以依次计算出所有的，于是就可以用求得。

所以我们就在的时间内计算出了个数的逆元。

代码实现

// C++ Version
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;

# Python Version
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