逆元 | wzy的博客

type

Post

status

Published

date

May 1, 2026

slug

niyuan

summary

什么是逆元？

在普通的算数中，除以一个数等于乘以它的倒数。但在“模运算”的世界里（即所有计算都在下进行），没有小数和分数。

定义： 如果两个整数 a 和 x 满足：

那么我们称是在模下的逆元，记作 $a^{-1}$。

💡

直观理解： 逆元就是模运算里的“倒数”。虽然看起来像分数，但在数论中它是一个 [0, p-1] 之间的整数。例如在模下，$3 times 5 = 15 equiv 1 pmod 7$，所以的逆元就是 $5$。

方法1：批量计算方法

时间复杂度O(n),but 可以计算1-n所有的逆元

第一步：建立等式

设我们要算的逆元，已知 $p = k cdot i + r$，其中：

$k = lfloor p / i rfloor$（商）

$r = p bmod i$（余数）

第二步：转换到模环境

因为模等于 $0$，所以：

第三步：移项与抵消

我们将移到等号右边：

为了求出的逆元$(i^{-1})$，我们需要想办法把右边的约掉。于是我们在等式两边同时乘以和 r^{-1}：

第四步：利用逆元性质

左边：$r cdot r^{-1}$ 抵消变为 $1$，剩下 $i^{-1}$。

右边：$i cdot i^{-1}$ 抵消变为 $1$，剩下 $-k cdot r^{-1}$。

最终得到：

3. C++ 线性递推实现（算法篇）

通过上面的推导，我们发现计算的逆元只需要知道 $r$（即 $p bmod i$）的逆元。因为永远比小，我们可以从小到大递推。

代码实现

为了处理数学中的负号 $-k$，在代码中我们使用 (p - p/i) 来代替，确保结果是正数。

[!important] 注意 1 的逆元永远是 1，所以初始化inv[1] = 1

4. 总结与应用

为什么这个算法重要？

除法变乘法：在处理大数取模时，你不能直接写 ans / a % p，必须写成 ans * inv[a] % p。

组合数计算：计算时，分母的必须通过逆元转为乘法。

效率极高：$O(n)$ 的复杂度意味着即便达到级别，计算机也能在秒内算完所有逆元。

总结公式：

方法二：费马小定理，时间复杂度`O(logn)`

1. 费马小定理 (Fermat's Little Theorem) 证明

定理陈述： 若是质数，$a$ 是一个不能被整除的整数，则 $a^{p-1} equiv 1 pmod p$。

证明方法：构造剩余系（Reduced Residue System）

考虑集合 $S = {1, 2, 3, dots, p-1}$。这里的每一个元素在模意义下都是唯一的。

我们将中的每一个元素都乘以 $a$，得到新集合 $S' = {1a, 2a, 3a, dots, (p-1)a}$。

关键点： 中的元素在模意义下仍然是互不相同的，且都不为 0。

证明： 若 $ia equiv ja pmod p$，由于 $gcd(a, p)=1$，根据消去律可知 $i equiv j pmod p$。既然是中不同的元素，那么在模下也必然不同。

因此，$S'$ 集合中的元素在模后，其实就是集合中元素的一个重新排列。

我们将两个集合中的元素分别累乘：

提取左边的 $a$：

由于是质数，$(p-1)!$ 与互质，我们可以直接约去 $(p-1)!$：

证毕。

2. 求逆元的方法证明

证明：

根据费马小定理：$a^{p-1} equiv 1 pmod p$

我们可以拆开一项 $a$：

对照逆元的定义 $a cdot x equiv 1 pmod p$，显然：

这就是为什么代码中写 power(a, p-2, p) 的原因。

3. 代码

公式$a^{p-2} mod p$ 很明显使用快速幂