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.求逆元的方法

单个数求逆元模板

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)。

模板题参考代码：

#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})。

模板题参考代码：

#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

有理数取余模板题

在本题中，p = 19260817，是个质数，故可以直接使用费马小定理求逆元。

但注意：

$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 指出本文在分析“欧拉定理求逆元”时的时间复杂度上的错误。

感谢 @WYXkk 提供了当 p 不是质数时，线性递推求模 p 意义下的逆元的方法。

Upd\,2019-8-23:

感谢 @Liuier 指出本文推导“离线逆元”的式子时出现的错误。

Upd\,2019-8-24:

当 p 不是质数时，线性递推求模 p 意义下的逆元的方法被证明是错误的……决定撤下QAQ

补充了逆元的完全积性的证明QwQ

感谢大家的阅读，再会！(^_−)☆