乘法逆元

定义

如果整数a, x满足, 则将x称为的模逆元， 记作.

模逆元也叫模倒数， 可以理解为模p同余式中a的倒数即, 也就是说， 模p的条件下， 是等价的。相似的有一些简单的性质如.

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

意义

当我们要求, 且b数值过大无法直接存储在变量中与a运算， 这时就可以使用乘法逆元。

由乘法逆元定义有。

求法

扩展欧几里得算法

过程

已知， 扩展欧几里得算法可用于求的一组可行解， 而当互质时， 。

代码实现

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为素数时互质的情况下求的逆元。

过程

由费马小定理， 当p为素数且a、p互质时， , 而a和a的逆元x满足， 即.

所以在满足上述条件时， 的逆元即为, 使用快速幂计算即可。

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的逆元。

过程

 

 

 

 

所以有递推式; 而对于始项1，事实上， 对于任意整数p， 都有 .

代码实现

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)