数论12_线性求逆元

吴老师

2026-08-23 15:02:39

发布于：广东

9阅读

0回复

0点赞

12 线性求逆元

学习目标

学完这一节，你应该能够：

理解为什么批量求逆元时需要更快的方法；
一步一步推出线性求逆元递推式；
理解为什么递推中出现的每一个逆元都存在；
理解为什么计算 inv[i] 时 inv[p % i] 已经算过；
独立写出线性求逆元代码。

1. 为什么需要批量求逆元

如果只求一个数的逆元，可以使用：

扩展欧几里得算法；
素数模下使用费马小定理加快速幂。

但如果要求：

$1,2,3,\dots,n$

在模 $p$ 下的所有逆元，一个一个使用快速幂，大约需要：

$O(n\log p)$

当：

$p$ 是素数；
$1\le n<p$ ；

时，可以利用一个递推公式，把总复杂度降到：

$\boxed{O(n)}$

2. 我们要求什么

令：

$inv[i]$

表示 $i$ 在模 $p$ 下的逆元。

也就是说：

$i\cdot inv[i]\equiv1\pmod p$

首先：

$1\times1\equiv1\pmod p$

所以：

$\boxed{inv[1]=1}$

接下来考虑怎样从前面已经求出的逆元得到 $inv[i]$ 。

3. 从带余除法开始

因为：

$i<p$

所以把 $p$ 除以 $i$ ：

$p=qi+r$

其中：

$q=\left\lfloor\frac pi\right\rfloor$

并且：

$r=p\bmod i$

余数满足：

$0\le r<i$

当 $i\ge2$ 时，因为 $p$ 是素数且 $i<p$ ，所以 $i$ 不可能整除 $p$ 。

因此：

$r\ne0$

所以：

$\boxed{1\le r<i}$

4. 把带余除法变成同余式

从：

$p=qi+r$

得到：

$qi+r=p$

两边模 $p$ 。

因为：

$p\equiv0\pmod p$

所以：

$qi+r\equiv0\pmod p$

把 $r$ 移到右边：

$qi\equiv-r\pmod p$

到这里还没有做任何“除法”，只是使用同余的加减法性质。

5. 第一次乘逆元：消去 $i$

因为：

$1\le i<p$

且 $p$ 是素数，所以：

$\gcd(i,p)=1$

因此 $i$ 在模 $p$ 下存在逆元 $i^{-1}$ 。

从：

$qi\equiv-r\pmod p$

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

$qi\cdot i^{-1}\equiv-r\cdot i^{-1}\pmod p$

因为：

$ii^{-1}\equiv1\pmod p$

所以：

$q\equiv-r i^{-1}\pmod p$

6. 第二次乘逆元：消去 $r$

前面已经证明：

$1\le r<i<p$

因为 $p$ 是素数，所以：

$\gcd(r,p)=1$

因此 $r$ 也存在逆元 $r^{-1}$ 。

从：

$q\equiv-r i^{-1}\pmod p$

两边同时乘 $r^{-1}$ ：

$qr^{-1}\equiv-r i^{-1}r^{-1}\pmod p$

因为：

$rr^{-1}\equiv1\pmod p$

所以：

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

两边同时乘 $-1$ ：

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

因此：

$\boxed{i^{-1}\equiv-qr^{-1}\pmod p}$

7. 换成程序中的写法

前面：

$q=\left\lfloor\frac pi\right\rfloor$

所以程序中：

q = p / i;

并且：

$r=p\bmod i$

对应：

r = p % i;

因此：

$inv[i]\equiv-\left\lfloor\frac pi\right\rfloor\cdot inv[p\bmod i]\pmod p$

为了把负号改成非负的同余代表，可以利用：

$-q\equiv p-q\pmod p$

得到：

$\boxed{inv[i]=\left(p-\left\lfloor\frac pi\right\rfloor\right)\cdot inv[p\bmod i]\bmod p}$

程序写成：

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

8. 为什么 `inv[p % i]` 一定已经算过

因为：

$r=p\bmod i$

并且：

$1\le r<i$

所以：

$p\bmod i<i$

程序按照：

$1,2,3,\dots,n$

从小到大计算。

当正在计算：

$inv[i]$

时，所有下标小于 $i$ 的逆元都已经算完。

而：

$p\bmod i<i$

所以：

$inv[p\bmod i]$

一定已经有值。

这就是这个递推能够从小到大进行的关键。

9. 用模 7 的例子一步一步计算

设：

$p=7$

9.1 $inv[1]$

$inv[1]=1$

9.2 $inv[2]$

$7=3\times2+1$

所以：

$inv[2]=(7-3)\cdot inv[1]\bmod7$

得到：

$inv[2]=4$

检查：

$2\times4=8\equiv1\pmod7$

9.3 $inv[3]$

$7=2\times3+1$

所以：

$inv[3]=(7-2)\cdot inv[1]\bmod7$

得到：

$inv[3]=5$

检查：

$3\times5=15\equiv1\pmod7$

9.4 $inv[4]$

$7=1\times4+3$

所以：

$inv[4]=(7-1)\cdot inv[3]\bmod7$

得到：

$inv[4]=6\times5\bmod7=2$

检查：

$4\times2=8\equiv1\pmod7$

10. C++ 模板

const int N = 1000000;
long long inv[N + 1];

void init_inv(int n, long long p) {
    inv[1] = 1;

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

11. 为什么要求 $p$ 是素数且 $n<p$

我们需要保证：

$1,2,\dots,n$

中的每个数在模 $p$ 下都有逆元。

当 $p$ 是素数，并且：

$1\le i\le n<p$

时：

$p\nmid i$

所以：

$\gcd(i,p)=1$

每个 $i$ 都存在逆元。

同时递推中的：

$r=p\bmod i$

也满足：

$1\le r<i<p$

所以 $r$ 也有逆元。

12. 为什么时间复杂度是 $O(n)$

循环：

for (int i = 2; i <= n; i++)

执行大约 $n$ 次。

每次只进行常数次：

整数除法；
取模；
乘法；
数组访问。

所以总时间复杂度是：

$\boxed{O(n)}$

13. 小练习

练习 1

为什么线性求逆元通常要求 $p$ 是素数并且 $n<p$ ？

练习 2

从：

$qi\equiv-r\pmod p$

开始，一步一步推出：

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

练习 3

为什么 inv[p % i] 一定在 inv[i] 之前算完？

14. 答案

练习 1

为了保证 $1,2,\dots,n$ 全部与 $p$ 互质，所以每一个逆元都存在。

练习 2

先两边乘 $i^{-1}$ ：

$q\equiv-ri^{-1}\pmod p$

再两边乘 $r^{-1}$ ：

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

最后两边乘 $-1$ ：

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

练习 3

因为：

$p\bmod i<i$

而程序按下标从小到大计算。

有帮助，赞一个

去预览

0/2000

这里空空如也

12 线性求逆元

学习目标

1. 为什么需要批量求逆元

2. 我们要求什么

3. 从带余除法开始

4. 把带余除法变成同余式

5. 第一次乘逆元：消去 iii

6. 第二次乘逆元：消去 rrr

7. 换成程序中的写法

8. 为什么 inv[p % i] 一定已经算过

9. 用模 7 的例子一步一步计算

9.1 inv[1]inv[1]inv[1]

9.2 inv[2]inv[2]inv[2]

9.3 inv[3]inv[3]inv[3]

9.4 inv[4]inv[4]inv[4]

10. C++ 模板

11. 为什么要求 ppp 是素数且 n<pn<pn<p

12. 为什么时间复杂度是 O(n)O(n)O(n)

13. 小练习

练习 1

练习 2

练习 3

14. 答案

练习 1

练习 2

练习 3

热门讨论

5. 第一次乘逆元：消去 $i$

6. 第二次乘逆元：消去 $r$

8. 为什么 `inv[p % i]` 一定已经算过

9.1 $inv[1]$

9.2 $inv[2]$

9.3 $inv[3]$

9.4 $inv[4]$

11. 为什么要求 $p$ 是素数且 $n<p$

12. 为什么时间复杂度是 $O(n)$