前言
本文讲解的是逆元的基本概念以及模意义下的乘法逆元，并介绍如何使用拓展欧几里得法，费马小定理法，线性递推法求乘法逆元。
一、什么是逆元
当我们在计算 a-b 时，可以将其视为 a+(-b) ；当我们计算 a/b 时，可以将其视为 a × (1/b) ，也就是乘以其倒数。逆元可以理解为在同余情况下的倒数。
在数论中，如果一个线性同余方程 $ax \equiv 1 (\mod p)$ ，则称 x 为 a mod p 意义下的逆元，记作 $a^{-1}$ 或 inv(a) 。在同余的情况下，除去一个数，等于乘以这个数的逆元，即 a/b(mod p) = a × inv(b)(mod p) 。
需要注意，逆元仅在所求数与模数互质，乘法逆元有两个性质：
- 在特定模数下唯一，不存在多解
- 乘法逆元是完全积性函数，也就是说 $inv(a) \times inv(b) = inv(a \times b)$
二、乘法逆元的作用
逆元有什么用呢？我们常常遇到一些题目要求结果对一个大质数 $p$ 取模，这是因为答案很大，出题人为了不麻烦大家写高精，就采取这样的方法。加减法和乘法对取模运算都是封闭的，所以我们可以步步取模来避免溢出，下图可以看出，一次取模和步步取模的结果是相同的。
但是当我们遇到除法的时候，步步取模就行不通了。根据下图可以看出，如果套用加减乘的步步取模公式，算出来的答案和一次取模的答案不一样。为什么除法是错的呢，证明也很简单：设 $a=k_0p+a' , b=k_1p+b' , k_0,k_1 \in Z$ ，可得 $(a\%p/b\%p) = (a'/b') = (a-k_0p)/(b-k_1p) \neq a/b$ 。
但是对于一些题目，我们必须在中间过程中进行求余，否则数字太大，电脑存不下，那如果这个算式中出现除法，我们就需要运用逆元了。根据上一节的概念可知，在模 p 意义下，$a/b$ 可以变形为 $a \times inv(b)$ 。实际上在模 10 意义下，$inv(3) = 7$ ，所以上图的式子可以转化为下图来运算：
三、如何求逆元
这里介绍三种计算逆元的方法：拓展欧几里得，费马小定理，线性递推。
拓展欧几里得法
拓展欧几里得法求逆元是一种较常用的求逆元方法，只要 $a$ 和模数 $p$ 互质，我们就可以使用它。实际上他与求同余方程的原理是一样的。当我们看到 $a \times inv(a) \equiv 1 (\mod p)$ 时，可以联想到方程 $a \times inv(a) + p \times y = 1$ 与 $a \times inv(a) \equiv 1 (\mod p)$ 是等价的。当 $a$ 与 $p$ 不互质时，方程无解，即没有逆元；当其互质时，将两者代入拓展欧几里得求一组可行解即可。为了防止负数，最后要做一步处理 $inv(a) = (inv(a)\%m + m)\%m$ 。
ll exgcd(ll a, ll b, ll &x, ll &y)// 拓欧
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
ll inv(ll a, ll p)
{
ll x, y;
if (exgcd(a, p, x, y) != 1) // 无解的情形
return -1;
return (x % p + p) % p;
}费马小定理法
费马小定理是数论中比较重要的定理，它的叙述如下：
若 $p$ 是质数，且 $gcd(a,p) = 1$ ，则有 $a^{p-1} \equiv 1(\mod p)$
我们从逆元的定义推导，可得 $a \times inv(a) \equiv 1 \equiv a^{p-1} (\mod p)$ ，于是有 $inv(a) \equiv a^{p-2}(\mod p)$ 。于是我们直接对 $a^{p-2}$ 计算快速幂即可。可以注意到，费马小定理求逆元只有在 $p$ 是质数的情况有效。
inline ll qpow(ll a, ll n, ll p)// 快速幂
{
ll ans = 1;
while (n)
{
if (n & 1)
ans = ans % p * a % p;
a = a % p * a % p;
n >>= 1;
}
return ans;
}
inline ll inv(ll a, ll p)
{
return qpow(a, p - 2, p);
}线性递推法
一般情况下上面两种方法就是我们常用的求逆元方法，但有些时候，题目如果要求连续一段大区间的所有数字的逆元，则有可能超时。这里 介绍逆元的线性递推求法（需保证$p$是质数）。
设 $p = aq + r$ ，即 $q = \lfloor p/a \rfloor , r = p\mod a$ 。
在模$p$意义下，有 $aq + r \equiv 0 (\mod p)$
移项整理得 $a = -r \times inv(q) (\mod p)$ 。
则 $inv(a) = -q \times inv(r) (\mod p)$ 。
即 $inv(a) = -\lfloor p/a \rfloor \times inv(p \mod a) (\mod p)$ 。
观察上面的式子可以发现一个数的逆元可以由比它小的数的逆元递推而来，因此我们可以用递推或者递归求解，时间复杂度为 $O(N)$ 。
// 递推写法
int inv[1000000];
void find_inv(int n,int p)//求1~n所有数模p意义下的逆元
{
inv[1]=1;//1的逆元就是1本身
for(int i=2;i<=n;i++)
inv[i]=(long long)(p-p/i)*(inv[p%i])%p; // (p-p/i)为了防止负数
//注意longlong，否则有可能导致溢出
}// 递归写法
// 多次对不同的p使用需要清空Inv数组
ll Inv[MAXN] = {0, 1};
inline ll mod(ll a, ll p)
{
return (a % p + p) % p;
}
ll inv(ll a, ll p)
{
if (Inv[a])
return Inv[a];
Inv[a] = mod(-p / a * inv(p % a, p), p);
return Inv[a];
}参考资料
版权属于：PCsky
本文链接：http://www.hyouka.club/index.php/archives/201/
转载时须注明出处及本声明