[数学]乘法逆元

# 0.前言 在 $OI$ 中，大多数情况下，善良的出题人为了避免高精度等大整数计算，常常会要求输出答案对一个数（大多是质数）取模的情况，但这衍生了一个问题：若题目中计算需用到除法而我们知道，如果 $a \equiv b \pmod{c}$ 在大部分情况下 $\lfloor \frac {a} {d} \rfloor \not\equiv \lfloor \frac {b} {d} \rfloor \pmod{c}$（注意一般题目会默认对一个数取模是数论（整数）意义上的取模，故这里除法为整数除法），这和等式的性质是不同的，要解决这个问题，就需要用到一个概念：乘法逆元。 本文主要介绍乘法逆元的定义以及其求法QwQ # 1.定义 如果您到百度上搜索逆元，您会看到如下定义：~~（这里逆元素是逆元的全称）~~ > 逆元素是指一个可以取消另一给定元素运算的元素 > > ---百度百科 这个定义似乎不太那么直观…… 我们来举个例子吧，先再实数范围举例，~~由小学知识可知~~，如果一个代数式 $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]$ 中的整数。 # 2.求逆元的方法 [单个数求逆元模板](https://www.luogu.org/problemnew/show/P1082) ## 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$ 我们可以通过不断迭代的方式来求解单个数的逆元，这里涉及到了解线性同余方程的知识，可以看我的[另一篇文章](https://1239004072angel.blog.luogu.org/post-shuo-xue-qiu-xie-yi-lei-fang-cheng-di-fang-fa) 我们发现这个方程有解的条件是 $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)$。 模板题参考代码： ```cpp #include <cstdio> #include <cstring> #include <iostream> using namespace std; long long a, b; int exgcd(long long a, long long b, long long &x, long long &y) { if (b == 0) { x = 1, y = 0; return a; } int d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } int main() { scanf("%lld%lld", &a, &b); long long x = 0, y = 0; exgcd(a, b, x, y); printf("%lld", (x % b + b) % b);//这里防止出现负数 return 0; } ``` ## 2.欧拉定理求逆元 观察式子 $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})$ 的时间内求出单个数的欧拉函数。 > 引理：设 $n = p_1^{k_1} \times p_2^{k_2} \times \cdots \times p_m^{k_m} = \prod_{i = 1}^{m} p_i^{k_i}$ 为正整数 $n$ 的质数幂乘积表示式，则： > > $\varphi(n) = n \times (1 - \frac {1} {p_1}) \times (1 - \frac {1} {p_2}) \times \cdots \times (1 - \frac {1} {p_m}) = n \times \prod_{i = 1}^{m} (1 - \frac {1} {p_i})$ 证明： 由于各质数幂之间是互质的，根据欧拉函数的性质可得： $$\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})$。 模板题参考代码： ```cpp #include <cstdio> #include <iostream> #include <algorithm> using namespace std; long long n, p; long long phi(long long x)//求x的欧拉函数 { long long res = x, tmp = x;//初始化答案为x for (int i = 2; i * i <= tmp; ++i) { if (x % i == 0) { res = (res / i) % p * ((i - 1) % p) % p;//找到x的一个质因子,计算其对答案的贡献 while (x % i == 0) x /= i;//统计完答案后,除去该质因子 } } if (x > 1) res = (res / x) % p * ((x - 1) % p) % p;//防止漏筛质因子 return res; } long long power(long long a, long long b)//快速幂 { long long res = 1; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res; } int main() { scanf("%lld%lld", &n, &p); long long tmp = phi(p) - 1; printf("%lld", power(n, tmp)); return 0; } ``` ## 3.费马小定理求逆元 **注意，这种求逆元的方法仅使用在 $p$ 为质数的时候** > 费马小定理：若 $p$ 为质数，且整数 $a$ 满足 $p \nmid a$，则有 $a^{p-1} \equiv 1 \pmod{p}$ 对于定理中的式子，我们可以将两边同除$a$，得： $$a^{p - 2} \equiv a^{-1} \pmod{p}$$ 而 $a^{-1}$ 就是 $a$ 在模 $p$ 意义下的乘法逆元。 故我们只需计算 $a^{p - 2}\,mod\,p$ 即可，而这个过程可用快速幂解决。 时间复杂度为 $O(\log p)$ 我们不妨看看本文开篇提出的问题，如何对一个分数取模？ 一般的讲，我们是这么定义分数取模的： 我们设 $\frac {a} {b}\,mod\,p$ 的值为一个整数 $x$，其满足 $bx \equiv a \pmod{p}$且 $x \in [0,p - 1]$。 我们只需求出 $x$ 的值即可。而上式两边同乘 $b$ 在模 $p$ 意义下的乘法逆元 $b^{-1}$ 后可得：$x \equiv ab^{-1} \pmod{p}$ 而 $x$ 的范围在模 $p$ 剩余系内，故可直接写作 $x = ab^{-1}\,mod\,p$ [有理数取余模板题](https://www.luogu.org/problem/P2613) 在本题中，$p = 19260817$，是个质数，故可以直接使用费马小定理求逆元。 但注意： $1.$ 当 $b \equiv 0 \pmod{p}$ 时，费马小定理不成立，故无解。 $2.$ 本题 $a,b$ 数据范围很大，$long\,long$ 也存不下，故需要写快读，边读边取模。 模板题参考代码： ```cpp #include <cstdio> #include <cstring> #include <cctype> #include <algorithm> #include <iostream> using namespace std; const int p = 19260817; template<typename T> inline void input(T &x) { x = 0; char ch = getchar(); bool f = false; while (!isdigit(ch)) { f |= (ch == '-'); ch = getchar(); } while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); x %= p;//边读边取模 ch = getchar(); } x = f ? -x : x; } inline int power(int a, int b)//快速幂 { int res = 1; while (b) { if (b & 1) res = 1ll * res * a % p; a = 1ll * a * a % p; b >>= 1; } return res; } int main() { int a, b; input(a), input(b); if (!b) puts("Angry!");//b % p = 0 时无解 else printf("%d", (int)(1ll * a * power(b, p - 2) % p)); return 0; } ``` ------ ## 4.线性求逆 [线性求逆模板题](https://www.luogu.org/problemnew/show/P3811) **注意，这种求逆元的方法仅使用在 $p$ 为质数的时候** 基于拓展欧几里得算法，我们虽然可以在 $O(n \log p)$ 时间内，求出 $[1,n]\,(1 \leq n < p)$ 中所有整数在模质数 $p$ 下的乘法逆元，但在面对更大的数据范围时，我们就需要更快的方法。 首先，我们不难发现，对于任何正整数 $c$ ，$1^{-1} \equiv 1 \pmod{c}$，即 $1$ 在模任意正整数意义下的逆元为其本身。 然后设 $p = ki + r\,(r < i,1 < i < p)$，将其转化为同余式会得到： $$ki + r \equiv 0 \pmod{p}$$ 两边同时乘 $i^{-1},r^{-1}$，得： $$i^{-1}r^{-1}(ki + r) \equiv 0 \pmod{p}$$ 将式子乘开： $$kr^{-1} + i^{-1} \equiv 0 \pmod{p}$$ 移项得： $$i^{-1} \equiv -kr^{-1} \pmod{p}$$ 由 $p = ki + r\,(r < i,1 < i < p)$ 易知 $k = \lfloor \frac {p} {i} \rfloor , r = p\,mod\,i$，故有： $$i^{-1} \equiv - \lfloor \frac {p} {i} \rfloor \times (p\,mod\,i)^{-1} \pmod{p}$$ 而 $p\,mod\,i < i$，故 $p\,mod\,i$ 的逆元我们之前已经递推出来了，故我们可以通过这个式子推出 $i$ 的逆元是谁。 综上，我们在已知 $1$ 的逆元为 $1$ 的情况下，可以推出 $[1,n]\,(1 \leq n < p)$ 中所有整数在模质数 $p$ 下的乘法逆元。 这个算法的时间复杂度为 $O(n)$。 注意 $- \lfloor \frac {p} {i} \rfloor$ 为负数，但在模 $p$ 意义下，其等价于 $p - \lfloor \frac {p} {i} \rfloor$，故在实际应用中真正的递推式为： $$i^{-1} \equiv (p - \lfloor \frac {p} {i} \rfloor) \times (p\,mod\,i)^{-1} \pmod{p}$$ 模板题参考代码： ```cpp #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 3e6 + 10; long long inv[maxn], n, p; int main() { scanf("%lld%lld", &n, &p); inv[0] = 0, inv[1] = 1;//初始化1的逆元为1 printf("%lld\n", inv[1]); for (int i = 2; i <= n; ++i) { inv[i] = (p - p / i) * inv[p % i] % p;//上文中的式子 printf("%lld\n", inv[i]); } return 0; } ``` ------ ## 5.离线逆元 [离线逆元模板题](https://www.luogu.org/problemnew/show/P5431) 在 2019 年十二省联考中某个 std 长达 800~~（900？）~~ 多行的题中用到了这个新知识。 ~~其实也不算全新的知识，似乎在以前这种方法只是被用来求阶乘逆元，最近才逐渐扩展到一般情况~~ 这个算法用途是：对于给定的 $n$ 个整数 $a_1,a_2,\cdots,a_n$，求它们在模 $p$ 意义下的乘法逆元。 $O(max(a_i))$ 的递推显然不适用，时间空间双双爆炸。 基于拓展欧几里得算法或费马小定理的 $O(n \log p)$ 的朴素算法也会超时，我们需要一种接近线性的算法。 我们不妨设 $pre_i$ 为 $a_1,a_2, \cdots ,a_i$ 的前缀积（即 $pre_i = \prod_{j = 1}^{i} a_j$） 然后我们就用到了一个 $trick$：**前缀积的逆元就是逆元的前缀积**（即逆元是完全积性的） 我们不妨来证明一下逆元是完全积性的，即证明对于任意正整数 $a,b$，它们在模 $p$ 意义下的逆元满足： $$a^{-1} \times b^{-1} \equiv (ab)^{-1} \pmod{p}$$ 根据逆元的定义，$a,b$ 在模 $p$ 意义下的逆元满足： $$a \times a^{-1} \equiv 1 \pmod{p} \quad b \times b^{-1} \equiv 1 \pmod{p}$$ 将两个式子相乘得： $$a \times b \times a^{-1} \times b^{-1} \equiv 1 \pmod{p}$$ 不难发现上式中 $a^{-1} \times b^{-1}$ 符合 $(ab)^{-1}$ 的定义，于是 $a^{-1} \times b^{-1} \equiv (ab)^{-1} \pmod{p}$，从而得证。 故我们利用费马小定理求出的 $pre_n$ 的逆元，它其实是 $a_1^{-1},a_2^{-1},\cdots,a_n^{-1}$ 的前缀积（即 $pre_n^{-1} = \prod_{j = 1}^{n} a_j^{-1}$） 而 $a_i^{-1} = \prod_{j = 1}^{i - 1} a_j \times \prod_{j = 1}^{i} a_j^{-1} = pre_{i - 1} \times pre_i^{-1}$，故我们求出可以从$n$开始，在求出 $pre_n^{-1}$ 后，利用 $pre_i^{-1} = a_{i + 1} \times \prod_{j = 1}^{i + 1} a_j^{-1} = a_{i + 1} \times pre_{i + 1}^{-1}$递推出 $pre_i^{-1}$，再用前文的式子递推出 $a_i^{-1}$ 即可。 综上，递推式为： $$pre_i^{-1} = a_{i+1} \times pre_{i + 1}^{-1}(1 \leq i < n)$$ $$a_j^{-1} = pre_{j - 1} \times pre_j^{-1}(1 \leq j \leq n)$$ （其中 $pre_n^{-1}$ 已求出，$pre_0 = 1$） 这种求逆元的方法的时间复杂度为 $O(n + \log p)$，已经接近线性。 模板题参考代码：（注意常数优化和防爆 $int$） ```cpp #include <cstdio> #include <cstring> #include <cctype> #include <iostream> #include <algorithm> using namespace std; template<typename T> inline void input(T &x)//本题卡常数,需要用快读 { x = 0; register char ch = getchar(); register bool f = false; while (!isdigit(ch)) { f |= (ch == '-'); ch = getchar(); } while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } x = f ? -x : x; } const int maxn = 5e6 + 10; int n, p, k, a[maxn], inv[maxn], pre[maxn], inv_pre[maxn]; inline int power(int a, int b, int p) { int res = 1; while (b) { if (b & 1) res = 1ll * res * a % p; a = 1ll * a * a % p; b >>= 1; } return res; } int main() { input(n), input(p), input(k); pre[0] = 1;//初始化 for (register int i = 1; i <= n; ++i) { input(a[i]); pre[i] = 1ll * pre[i - 1] * a[i] % p;//计算前缀积 } inv_pre[n] = power(pre[n], p - 2, p);//求出前缀积的逆元 for (register int i = n; i > 0; --i)//递推求逆元 { inv[i] = 1ll * pre[i - 1] * inv_pre[i] % p; inv_pre[i - 1] = 1ll * inv_pre[i] * a[i] % p; } int ans = 0;//计算题目中式子的值 for (register int i = 1, t = k; i <= n; ++i) { ans = (1ll * inv[i] * t % p + ans) % p; t = 1ll * t * k % p; } printf("%d", ans); return 0; } ``` ------ # 3.后记 本文部分参考了《信息学奥赛之数学一本通》（东南大学出版社）中的内容。 $Upd\,2019-8-21:$ 感谢 @[_Wallace_](https://www.luogu.org/space/show?uid=61430) 指出本文在分析“欧拉定理求逆元”时的时间复杂度上的错误。 感谢 @[WYXkk](https://www.luogu.org/space/show?uid=130151) 提供了当 $p$ 不是质数时，线性递推求模 $p$ 意义下的逆元的方法。 $Upd\,2019-8-23:$ 感谢 @[Liuier](https://www.luogu.org/space/show?uid=163874) 指出本文推导“离线逆元”的式子时出现的错误。 $Upd\,2019-8-24:$ 当 $p$ 不是质数时，线性递推求模 $p$ 意义下的逆元的方法被证明是错误的……决定撤下QAQ 补充了逆元的完全积性的证明QwQ 感谢大家的阅读，再会！(^_−)☆