逆元

定义

非零实数 $a \in \mathbb{R}$ 的乘法逆元即为它的倒数 $a^{-1}$ ，类似地，在模 $p$ 意义下，我们可以定义 $a$ 的乘法逆元 $a^{-1} \,\, mod \,\, m$ ，即为模逆元。

标准定义：

这相当于 $b$ 是线性同余方程 $ax \equiv 1 (mod \,\, m)$ 的解，则当且仅当 $gcd(a,m) = 1$ 时，方程有解即 $a$ 的逆元存在。

求解方法

费马小定理快速幂法

这一方法主要适用于 $m$ 为素数的情形。

首先，有费马小定理

其中 $p$ 为素数，且 $gcd(a,p) = 1$

我们要对线性同余方程

求解，可以发现存在解为

则此时

$x$ 即为 $a$ 在模 $p$ 意义下的逆元，使用快速幂求解。时间复杂度为 $O(log \, p)$

1
2
3
4
5
6
7
8
9
10
11
12// Binary exponentiation.
int pow(int a, int b, int m) {
  long long res = 1, po = a;
  for (; b; b >>= 1) {
    if (b & 1) res = res * po % m;
    po = po * po % m;
  }
  return res;
}

// Returns the modular inverse of a prime modulo p.
int inverse(int a, int p) { return pow(a, p - 2, p); }

扩展欧几里得算法

此方法适用于任意正整数 $m$ 满足 $gcd(a,m) = 1$

可知求解线性同余方程

即等价于求解二元一次不定方程

其中 $x$ 即为所求逆元，此时可用扩展欧几里得算法求解。时间复杂度为 $O(log \, min\{a,m\})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18// Extended Euclidean algorithm.
void ex_gcd(int a, int b, int& x, int& y) {
  if (!b) {
    x = 1;
    y = 0;
  } else {
    ex_gcd(b, a % b, y, x);
    y -= a / b * x;
  }
}

// Returns the modular inverse of a modulo m.
// Assumes that gcd(a, m) = 1, so the inverse exists.
int inverse(int a, int m) {
  int x, y;
  ex_gcd(a, m, x, y);
  return (x % m + m) % m;
}

线性递推

此方法适用于对前 $n$ 个整数进行批量求逆元。

我们设 $inv_i$ 为 $i$ 在模 $p$ 意义下的逆元。

首先，对于 $n=1$ ，有逆元 $inv_1 = 1$

从而对于任意正整数 $1 < i \le n$ ，考虑带余除法。

其中 $q = \lfloor \dfrac {p}{i} \rfloor ,r = p \,\, mod \,\, i$

两边对 $p$ 取模，得到

两边同时乘以 $inv_i \cdot inv_r$ 得

从而

又 $r < i$ ，则显然对任意正整数 $i$ 均可由该地推关系计算得到逆元。

总体时间复杂度为 $O(n)$

前缀积逆推

设有序列 $a_1,a_2, \dots ,a_n$ ，要求出它们的逆元。若直接使用扩欧或者快速幂计算逆元，则时间复杂度为 $O(nlog \, p)$ ，现在给出 $O(n)$ 的方法。

首先计算前缀积 $pre_n = a_1a_2 \dots a_n \,\, (mod \,\, p)$ ，然后计算 $prefix_n$ 的逆元 $inv_{pre_n}$

随后观察逆推关系，显然我们有：

则:

又可知在模 $p$ 意义下， $\dfrac {pre_k}{pre_{k-1}} = pre_k \cdot inv_{pre_{k-1}}$

两边同时求逆元得：

则我们只需要求出所有的 $inv_{pre_i}$ ，如何求解呢？同样是使用递推关系来求解。

同样的，有：

两边同时求逆元得：

同理，模 $p$ 意义下，$\dfrac {inv_{pre_k}}{inv_{a_k}} = inv_{pre_k} \cdot a_k$

综上，有：

通过这个方法，可以做到逆推求解每个 $a_i$ 的逆元。