定义

如果整数a, x满足$ax\equiv 1(modp)$, 则将x称为$amodp$的模逆元， 记作$a^{-1}$.

模逆元也叫模倒数， 可以理解为模p同余式中a的倒数即$\frac{1}{a}$, 也就是说， 模p的条件下， $a\mathrm{和}x$是等价的。相似的有一些简单的性质如$(ab{)}^{-1}\equiv (a{)}^{-1}\ast (b{)}^{-1}(modp)，(\frac{b}{a}{)}^{-1}\equiv \frac{a}{b}(modp),1^{-1}\equiv 1(modp)$.

注意， a在模p条件下存在逆元的充分必要条件是， a与p互素。

意义

当我们要求$(\frac{b}{a})\mathrm{mod}p$, 且b数值过大无法直接存储在变量中与a运算， 这时就可以使用乘法逆元。

由乘法逆元定义有$bax\equiv b(modp)⟺bx\equiv \frac{b}{a}(modp)$。

求法

扩展欧几里得算法

过程

已知， 扩展欧几里得算法可用于求$ax+by=gcd(a,b)$的一组可行解， 而当$a、b$互质时， $ax+by=gcd(a,b)⟺ax+by=1⟺ax\equiv 1(modb)$。

代码实现

python

def exgcd(a, b):
    if b == 0: 
        return 1, 0
    x, y = exgcd(b, a % b)
    return y, x - y*(a // b)
ans = (exgcd(a, p)[0] % p + p) % p # 求a关于p的逆元

费马小定理

费马小定理可用于在p为素数时互质的情况下求$amodp$的逆元。

过程

由费马小定理， 当p为素数且a、p互质时， $a^{p-1}\equiv 1(\mathrm{mod}p)$, 而a和a的逆元x满足$ax\equiv 1(\mathrm{mod}p)$， 即$a^{p-1}\equiv ax(\mathrm{mod}p)⟺x\equiv a^{p-2}(\mathrm{mod}p)$.

所以在满足上述条件时， $a(modp)$的逆元即为$a^{p-2}(\mathrm{mod}p)$, 使用快速幂计算即可。

python

代码实现

def quick_pow(a, n, p):
    ans = 1
    while n:
        if n & 1:
            ans = ans * a % p
        a = a * a % p
        n >>= 1
    return ans
ans = quick_pow(a, p - 2, p) # 求a关于p的逆元

线性求逆元(递推)

递推法用于求[1, a]区间的每个数mod p的逆元。

过程

$p\mathrm{\%}a=p-a\lfloor \frac{p}{a}\rfloor$ \

$\Rightarrow p\mathrm{\%}a\equiv -a\lfloor \frac{p}{a}\rfloor (modp)$ \

$\Rightarrow a\equiv (p\mathrm{\%}a)/(-\lfloor \frac{p}{a}\rfloor )(modp)$\

$\Rightarrow a^{-1}\equiv -\lfloor \frac{p}{a}\rfloor (p\mathrm{\%}a{)}^{-1}(modp)$\

所以有递推式$inv[n]\equiv -\lfloor \frac{p}{n}\rfloor \ast inv[p\mathrm{\%}n](modp)$; 而对于始项1，事实上， 对于任意整数p， 都有$1\ast 1\equiv 1(modp)$ .

代码实现

c++

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
  inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}

参考

乘法逆元的几种计算方法 | Menci's OI Blog

乘法逆元 - OI Wiki (oi-wiki.org)

乘法逆元详解 - MJT12044 - 博客园 (cnblogs.com)