求乘法逆元-JZTXT

「观前提醒」

「文章仅供学习和参考，如有问题请在评论区提出」

前提公式
求解
参考资料

前提公式

同余式

如果整数 $a, b$ 模 $m$ 的余数相同，则称 $a, b$ 模 $m$ 同余，记为 $a \equiv b \pmod{m} $ 。

乘法逆元

若 $a, b$ 互质，且满足同余方程 $ax \equiv 1 \pmod{b}$ ，则称 $x$ 为 $a$ 模 $b$ 的乘法逆元，记作 $a^{-1}$ 。

例如：$8x \equiv 1 \pmod{5} $ ，解得 $x = 2, 7, 12...$ 。

费马小定理

若 $p$ 为质数，且 $a, p$ 互质，则 $a^{p - 1} \equiv 1 \pmod{p} $ 。

求解

对于 $a, p(a < p)$ ，$p$ 是质数，求 $a$ 模 $p$ 的乘法逆元。

由费马小定理，$a^{p - 1} \equiv 1 \pmod{p} $ ，那么有 $a \times a^{p - 2} \equiv 1 \pmod{p} $ ，所以 $a^{p - 2}$ 就是 $a$ 模 $p$ 的乘法逆元。

利用快速幂，时间复杂度为 $O(logp)$

typedef long long LL;

// 快速幂
int qmi(int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * (LL)a % p;
        a = a * (LL)a % p;
        k >>= 1;
    }
    return res;
}

int A = qmi(a, p - 2, p);	// a 模 p 的乘法逆元

参考资料

521 同余式乘法逆元费马小定理_董晓算法