Skip to content

乘法逆元

2021-08-19

INFO

若无特殊说明,本章涉及的变量皆为正整数。

定义

ab1(modp),则 ba 在模 p 意义下的逆元,记作 a1inv(a)

a·a11(modp)

乘法逆元能够很好地将模运算中的除法转为乘法:

abab1(modp)

在模运算中,a1 是整数,并不是 a1 次方。

解法

对于整数 x,可以求解关于 x1线性同余方程 xx11(modp),其中 x 为已知常数。

cpp
int exGcd(int a, int b, int& x, int& y) {
    if(b == 0) { x = 1, y = 0; return a; }
    int d = exGcd(b, a % b, x, y);
    int t = x; x = y, y = t - a / b * y;
    return d;
}

int liEu(int a, int b, int c) { // a·x ≡ c (mod b)
    int x, y, d = exGcd(a, b, x, y);
    x *= (c / d);
    int t = b / d;
    return (x % t + t) % t;
}

int inv(int x, int m) {
    return liEu(x, m, 1);
}

模为质数的逆元

p 为质数时,由 费马小定理 得:

ap11(modp)ap2a1(modp)

p1=ap2modp,其中 ap2 可用 快速幂 求解。

线性求逆元

1n 在模 p 意义下的逆元。

假设已经求出了 1i1 的乘法逆元。

m=pmodi=ppii,则有:

m+pii0(modp)

两边同乘 m1i1

i1+pim10(modp)

由于 m=pmodii1,所以 m1 已知. 于是得到 i1 的表达式:

i1=(pi(pmodi)1)modp
cpp
inv[1] = 1; // 1 的乘法逆元 = 1
for (int i = 2; i <= n; i ++) {
    inv[i] = (- p / i * inv[p % i]) % p;
    inv[i] = (inv[i] + p) % p; // 化为正整数
}