前言

在学校科技协会面试的时候被乘法逆元给单杀了，所以来严肃重新学习一下乘法逆元。

定义

对于整数 (a) 和模数 (m)，如果存在整数 (x)，使得：

$$a x \equiv 1 \pmod m $$

那么称 (x) 是 (a) 在模 (m) 意义下的乘法逆元，记作：

$x\equiv a^{-1}\pmod m$

乘法逆元存在的充要条件是：

$$ gcd(a,m)=1 $$

例如，模 (7) 下，(3) 的逆元是 (5)，因为：

$$ 3\times 5=15\equiv 1\pmod 7 $$

乘法逆元常用于模意义下的除法，例如：

$$ \frac{a}{b}\pmod m $$

可以转化为：

$$ a\cdot b^{-1}\pmod m $$

也就是说，模运算中的“除法”通常通过乘以除数的逆元来实现。

费马小定理法

费马小定理：若 $p$ 是质数且 $\text{gcd}(a,p)=1$ ，则 $a^{p-1} \equiv 1 \pmod p$

于是，根据费马小定理，可以推出：

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

回去看看乘法逆元的定义，发现：

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

所以我们只需要用快速幂求出 $a^{p-2} \bmod p$ 就求出了 $a$ 在模 $p$ 意义下的乘法逆元。

而该方法的条件显然就是 $p$ 是素数且 $p \nmid a$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
long long qpow(long long a, long long e, long long mod) {
    long long res = 1;
    while (e) {
        if (e & 1) res = res * a % mod;
        a = a * a % mod;
        e >>= 1;
    }
    return res;
}

// 求 a 在质数 mod 下的乘法逆元
long long inv(long long a, long long mod) {
    return qpow(a, mod - 2, mod);
}

扩展欧几里得法

裴蜀定理：对于任意整数 $a,b$ 存在整数 $x,y$ 使得 $ax+by=\text{gcd}(a,b)$ 。

在计算乘法逆元的时候，如果 $\text{gcd}(a,m)=1$，那么根据裴蜀定理就有：

$$ax+my=1$$

两边同时对 $m$ 取模，有：

$$ax+my \equiv 1 \pmod m$$

因为 $my$ 是 $m$ 的倍数，所以有：

$$my \equiv 0 \pmod m$$

综上，有：

$$ax \equiv 1 \pmod m$$

而扩展欧几里得算法就是用来解决 $ax+by=\text{gcd}(a,b)$ 解出 $x,y$ 的，所以此时解出的 $x$ 就是 $a$ 在模 $m$ 意义下的逆元。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
long long exgcd(long long a, long long b,
                long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    long long x1, y1;
    long long g = exgcd(b, a % b, x1, y1);

    x = y1;
    y = x1 - (a / b) * y1;

    return g;
}

long long inv(long long a, long long mod) {
    long long x, y;
    long long g = exgcd(a, mod, x, y);

    // 逆元不存在
    if (g != 1) {
        return -1;
    }

    // 将结果调整到 [0, mod - 1]
    return (x % mod + mod) % mod;
}

线性递推法

线性递推法适用于模数 $p$ 是素数的情况，可以 $O(n)$ 的时间复杂度求出 $1,2,…,n$ 的逆元。

设 $inv[i] \equiv i^{-1} \pmod p$ ，显然 $inv[1]=1$。

带余除法：对于任意的正整数 $p,i$ ，都存在唯一整数商 $q$ 和余数 $r$ ，满足：$p=qi+r,0 \le r<i$。

对于$i>1$，进行带余除法，得到：

$$p=\lfloor\frac{p}{i}\rfloor i+(p\bmod i)$$

可以推出：

$$p \bmod i=p-\lfloor\frac{p}{i}\rfloor$$

在模 $p$ 下：

$$p \bmod i \equiv -\lfloor\frac{p}{i}\rfloor \pmod p$$

两边同时乘上 $i^{-1}$和$(p \bmod i)^{-1}$ ，可得：

$$inv[i] \equiv -\lfloor \frac{p}{i} \rfloor inv[p \bmod i] \pmod p$$

负数取模：$-x \bmod p=(p-(x \bmod p))\bmod p$

所以递推公式就是：

$$inv[i]=p-\lfloor\frac{p}{i}\rfloor inv[p \bmod i] \bmod p$$

1
inv[i] = (p - 1LL * (p / i) * inv[p % i] % p) % p;

前缀积法

前缀积法用于一次求出多个数的乘法逆元。核心思想是：先把所有数乘起来，只求一次总乘积的逆元，再倒推每个数的逆元。

设需要求：

$$a_1^{-1},a_2^{-1},\dots,a_n^{-1}\pmod m$$

并且每个 $a_i$ 都与 $m$ 互质。

我们定义前缀积：$pre[i]=\prod_{j=1}^{i} a_{j} \pmod m$，可以用类似前缀和的思想快速预处理。

我们只需要计算一次 $pre[n]$ 的逆元，记为 $s$，然后从后往前倒推：

$$a_i^{-1}=pre[i-1]\times s \pmod m$$

原因是$pre[i-1] \times s=\prod_{j=1}^{i-1} a_j\times\prod_{j=1}^{i-1}a_j^{-1}$，两边约掉前面的因子正好得到$a^{-1}$和后缀逆元。

然后更新$s\leftarrow s\times a_i\pmod m$。

这样就可以处理 $a_{i-1}$ 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<long long> pre(n + 1), inv(n);

pre[0] = 1;
for (int i = 1; i <= n; i++) {
    pre[i] = pre[i - 1] * a[i] % mod;
}

long long s = qpow(pre[n], mod - 2, mod); // mod 为质数时

for (int i = n; i >= 1; i--) {
    inv[i] = pre[i - 1] * s % mod;
    s = s * a[i] % mod;
}