前言：
还记得小学学的倒数吗？倒数的定义大概是若 \(ax = 1\)，则称 \(x\) 为 \(a\) 的倒数。而逆元，其实可以看做在模意义下的倒数。也就是 \(ax \equiv 1 \pmod p\)，且 \(a\) 与 \(p\) 互质，则称 \(x\) 为 \(a\) 在模 \(p\) 意义下的乘法逆元，记作 \(a^{-1}\)。本文就将简要介绍求逆元的三种常用方法。
例题：
给定正整数 \(n\) 和 \(p\)，求 \(n\) 以内正整数在模 \(p\) 意义下的乘法逆元。
保证 \(p\) 是质数。
解法：
1.费马小定理：
费马小定理的定义：
对于任意正整数 \(a\) 和质数 \(p\)，有 \(a^{p-1} \equiv 1\pmod p\)。
可以发现，费马小定理的式子很像逆元，考虑把它转化一下，变成：
\(a \times a ^ {p-2} \equiv 1\pmod p\)。
可以发现，\(a^{p-2}\) 就等于上面的 \(x\)，即 \(a^{p-2}\) 就是 \(a\) 在模 \(p\) 意义下的乘法逆元，用快速幂求即可。
点击查看代码
int qpow(int a, int b, int mod)
{
int ans = 1;
a %= mod;
while(b)
{
if(b & 1) ans *= a;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int inv(int a, int p)//求a在模p意义下的乘法逆元
{
return qpow(a, p - 2, p);
}
2.\(\operatorname{Exgcd}\)：
不知道 \(\operatorname{exgcd}\) 的可以参考我的博客
考虑将原式转换为 \(ax+py=1\) (注：\(y\) 是引入的一个整数，而且可能是负数)，根据逆元的定义：\(a\)，\(p\) 必须互质，也就是 \(\gcd(a, p) = 1\)，因此原方程一定有解，用 \(\operatorname{exgcd}\) 求即可。
点击查看代码
void exgcd(int a, int b, int &x, int &y)
{
if(b == 0)
{
x = 1; y = 0;
return;
}
exgcd(b, a % b, y, x);
y = a / b * x;
}
int inv(int a, int p)//求a在模p意义下的乘法逆元
{
int x, y;
return exgcd(a, p, x, y);
}
3.线性递推：
很多时候，题目要求的都是像例题那样 \(1\)~\(n\) 的逆元，用上面两种办法可以达到较快的 \(O(n\log n)\) 的复杂度（其实费马小定理得复杂度应该为 \(O(n\log q)\)。不过有没有方法能在线性时间内求出呢？答案是有的。
注：下面笔者提供了两种介绍方法，前一种为严谨的数学证明，后一种是转化为 \(\operatorname{exgcd}\) 的介绍，请读者根据需要自行阅读。
- 数学证明：
先给结论：\( \begin{cases} x=1 & a=1 \\ -\frac{q}{a}(p\mod a)^{-1} & otherwise \\ \end{cases} \)
先把式子转化一下：
设 \(k=\frac{p}{a}\), \(b=p\mod a\)。
则 \(a=\frac{p-b}{k}\)
则原式就可以变成：
\(a(-\frac{p}{a}(p\mod a)^{-1})=a(-kb^{-1})\)
打开括号，变成：
\(-xkb^{-1}=-k\frac{m-b}{k}b^{-1}\)
把 \(k\) 消掉，得到：
\((b-p)b^{-1}\)
因为对于同余方程，增减带模数的项结果不发生改变，所以可以将 \(p\) 去掉，变为：
\((b-p)b^{-1} \equiv bb^{-1} \equiv1 \pmod m\)
换句话说，\(a(-\frac{q}{a}(q\mod a)^{-1})=a(-kb^{-1}) \equiv1 \pmod m\)，即 \(-\frac{q}{a}(q\mod a)^{-1})=a(-kb^{-1}=a^{-1}\)。】
- 其实仔细观察可以发现，上式其实与 \(\operatorname{exgcd}\) 的结论的式子很像。加上之前逆元对 \(\operatorname{exgcd}\) 的转化，就显而易见了，具体一点笔者也说不清，请读者自行脑补（大雾。
知道上面的结论，代码就好写了。用一个数组记录每个数的逆元，正序枚举，由于枚举到 \(i\) 时，\(1\)~\(i-1\) 的逆元都已算出，因此 \(i\mod p\) 的逆元也能求出，便可以做到单次 \(O(1)\)，总复杂度为 \(O(n)\)。
1
点击查看代码
inv[1] = 1;//inv[i] = i^ -1
cout << 1 << "\n";
for(int i = 2; i <= n; i++)
{
inv[i] = (p - p / i) * inv[p % i] % p;//按公式计算。
//之所以要p-p/i是因为除完之后是个负数，在后面的取模会有问题，因此按照负数取模的原理要减一下
cout << inv[i] << "\n";
}
总结：
至此，逆元就告一段落了，文中的三种方法都有不错的时间复杂度，在应用中请根据实际情况选择，希望本文能帮助到您。
鉴于笔者也是蒟蒻，文中给出的部分推导过程与表述可能不严谨，欢迎大佬在评论区指出。
同时如果您对文章内容有不理解的地方，欢迎随时提问。