逆元课堂笔记

AAA光碟批发白蛇

2026-08-27 15:33:59

发布于：上海

5阅读

0回复

0点赞

为什么需要逆元

在模意义下，加、减、乘法均满足分配律，唯独除法不满足分配律。 $(10 / 2)\bmod 3 = 2,((10\mod 3) / 2)\bmod 3 = 0.5\bmod 3$
为了解决除法取模的问题，我们定义： $ax \equiv 1\pmod p$ ，则称 $x$ 是 $a$ 在模 $p$ 意义下的乘法逆元，记作 $a^{-1}$ 。
有了逆元，就可以把除法转化为乘法： $\dfrac{a}{b} \equiv a \times b^{-1}\pmod p$

exgcd求逆元

求 $a$ 模 $p$ 的逆元，等价于求解方程：

$ax \equiv 1 \pmod p\iff ax + py = 1$

适用场景： $a$ ， $p$ 必须互质，但不要求 $p$ 是质数。
【exgcd模板】

long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    long long x2, y2;
    long long g = exgcd(b, a % b, x2, y2);
    x = y2;
    y = x2 - (a / b) * y2;
    return g;
}

费马小定理+快速幂求逆元

费马小定理：若 $p$ 为质数，且 $gcd(a , p) = 1$ ，则有

$a^{p - 1} \equiv 1 \pmod p\implies a \times a^{p - 2} \equiv 1 \pmod p$

适用场景： $a , p$ 必须互质， $p$ 必为质数

long long qpow(long long a, long long b, long long p) {
    long long res = 1;
    a %= p;
    while (b > 0) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}