【洛谷日报#205】乘法逆元

在 OI 中，大多数情况下，善良的出题人为了避免高精度等大整数计算，常常会要求输出答案对一个数（大多是质数）取模的情况，但这衍生了一个问题：若题目中计算需用到除法而我们知道，如果 a \equiv b \pmod{c} 在大部分情况下 \lfloor \frac {a} {d} \rfloor \not\equiv \lfloor \frac {b} {d} \rfloor \pmod{c} （注意一般题目会默认对一个数取模是数论（整数）意义上的取模，故这里除法为整数除法），这和等式的性质是不同的，要解决这个问题，就需要用到一个概念：乘法逆元。

本文主要介绍乘法逆元的定义以及其求法QwQ

如果您到百度上搜索逆元，您会看到如下定义：（这里逆元素是逆元的全称）

这个定义似乎不太那么直观……

我们来举个例子吧，先再实数范围举例，由小学知识可知，如果一个代数式 F 乘一个数 a 后，再乘它的倒数 \frac {1} {a} ，相当于没有乘 a （这里不考虑 0 的情况），换句话说，我们乘 \frac {1} {a} 后，取消了代数式 F 乘 a 后值增大的影响。

不难发现这符合逆元的定义，故我们可以说一个数和其倒数互为乘法逆元。除此之外，我们还能发现一个数和其相反数互为加法逆元等等……

接下来回到代数式的例子，考虑为什么 a 的倒数 \frac 1 a 能消去乘 a 的影响。显然，是由于乘法结合律的存在，使得我们在运算 F \times a \times \frac 1 a 时可以先运算 a \times \frac 1 a 的值，再运算它和 F 的乘积，而 a \times \frac 1 a = 1 ，任何数与 1 的乘积均为其本身，从而使乘 a 对 F 值增大的影响取消。

上文在实数范围内讨论了乘法逆元，现在我们来看本文主要讨论的内容，数论模意义下的乘法逆元。

由上文的分析来看，我们可以借助“任何数与 1 的乘积均为其本身”的性质定义模意义下的乘法逆元。

故其定义为：如果说 a 在模 p 意义下的乘法逆元是 x ，那么 ax \equiv 1 \pmod{p}

我们通常将 a 的逆元记作 a^{-1} 。

如同 0 没有倒数一样， 0 也没有乘法逆元。

不难发现， a 在模 p 意义下的乘法逆元均为 [1,p - 1] 中的整数。

单个数求逆元模板

不难发现 ax \equiv 1 \pmod {p} 可以写成 ax + py = 1 的形式：

将同余号换为等号得：

ax\,mod\,p = 1\,mod\,p \\

移项得：

(ax - 1)\,mod\,p = 0 \\

由上式可知 ax - 1 为 p 的整数倍，不妨设其为 p 的 k(k \in Z) 倍：

ax - 1 = kp \\

继续移项得：

ax - kp = 1 \\

令 y = -k ，就写成了上文的形式： ax + py = 1

我们可以通过不断迭代的方式来求解单个数的逆元，这里涉及到了解线性同余方程的知识，可以看我的另一篇文章

我们发现这个方程有解的条件是 gcd(a,p) \mid 1 ，即 gcd(a,p) = 1 ， a,p 互质，所以得出结论： a 在模 p 意义下的乘法逆元存在当且仅当 a,p 互质，这也在一定程度上解释了大多数题目模数为什么为质数的原因：（设模数为 p ）可以保证在 [1,p - 1] 中的所有整数都有模 p 意义下的逆元。

而由于 gcd(a,p) = 1 ，故我们可以直接运用拓展欧几里得算法解 ax + py = gcd(a,p) 这个方程。

时间复杂度为 O(\log p) 。

模板题参考代码：

观察式子 ax \equiv 1 \pmod{p} ，我们发现它和欧拉定理 a^{\varphi(p)} \equiv 1 \pmod{p} 很像……

而欧拉定理又是 a,p 互质时成立，这和逆元存在的条件相同……

故将两个式子合在一起，得：

ax \equiv a^{\varphi(p)} \pmod{p} \\

两遍同除 a 得：

x \equiv a^{\varphi(p) - 1} \pmod{p} \\

故 x = a^{\varphi(p) - 1}\,mod\,p

我们可以在 O(\sqrt{p}) 的时间内求出单个数的欧拉函数。

证明：

由于各质数幂之间是互质的，根据欧拉函数的性质可得：

\begin{aligned} \varphi(n) = \prod_{i = 1}^{m} \varphi(p_i^{k_i}) \ = \prod_{i = 1}^{m} p_i^{k_i} \times \prod_{i = 1}^{m} (1 - \frac {1} {p_i}) \ = n \times \prod_{i = 1}^{m} (1 - \frac {1} {p_i}) \end{aligned} \\

进而得证。

在求一个数的欧拉函数时，不妨将上式后面的分数部分通分化作 \varphi(n) = n \times \prod_{i = 1}^{m} (\frac {p_i - 1} {p_i}) ，我们可以在 O(\sqrt{n}) 的时间内枚举 n 的每个质因子，初始化 ans 为 n ，每枚举到一个质因子 p_i 就让 ans \times \frac {p_i - 1} {p_i} ，发现每个质因子只对答案贡献一次，故在统计完该质因子的答案后，这个质因子就无用了，为了方便最后判断我们是否将 n 的所有质因子全都枚举到，我们可以通过不断除该质因子来消去它，防止其再被计入答案。

求出欧拉函数后，可以使用快速幂求出答案。

故这样做的时间复杂度为 O(\log \varphi(p) + \sqrt{p}) 。

模板题参考代码：