乘法逆元 总结

理论

若存在一个数 \(x\) 使得 \(ax \equiv 1 \pmod{m}\) 则称 \(x\) 为 \(s\) 的逆元，记作 \(a^{-1}\)。

逆元存在的充要条件：\(a, m\) 互质

证明：

• 必要性：若 \(\gcd(a, m) = d > 1\)，因为 \(ax \equiv 1 \pmod{m}\)，所以 \(ax + my = 1\)，但 \(d \mid ax + my\)，所以 \(d \mid 1\)，矛盾
• 充分性：若 \(\gcd(a, m) = 1\)，则 \(ax + my = 1\)，即 \(ax \equiv 1 \pmod{m}\)

求法

求法 1 扩欧求逆元

原理：把同余方程 \(ax \equiv 1 \pmod{m}\) 转化为 \(ax + my = 1\)

优点：提醒判无解

时间：\(O(\log n)\)

求法 2 费马小求逆元（要求 \(p\) 为质数）

费马小定理：若 \(p\) 为质数且 \(a, p\) 互质，则有 \(a^{p - 1} \equiv 1 \pmod{p}\)，此时 \(a^{-1} \equiv a^{p - 2} \pmod{p}\)

条件：要求 \(p\) 为质数且 \(a, p\) 互质

时间：\(O(\log n)\)

求法 3 递推求逆元

递推式：\(inv[i] = ((p - \left\lfloor\dfrac{p}{i}\right\rfloor) \times inv[p \bmod i]) \bmod p\)

证明：

令 \(p = ki + r\)，其中 \(k = \left\lfloor\dfrac{p}{i}\right\rfloor, r = p \bmod i\)

\[ki + r \equiv 0 \pmod{m} \]

\[kr^{-1} + i^{-1} \equiv 0 \pmod{m} \]

\[i^{-1} \equiv -kr^{-1} \pmod{m} \]

\[i^{-1} \equiv (p - k)r^{-1} \pmod{m} \]

时间：\(O(n)\)

求法 4 阶乘的逆元

过程：

1. 求 \([1, n]\) 的阶乘
2. 求 \(n!\) 的逆元
3. \(inv[i] = (inv[i + 1] \times (i + 1)) \bmod p\)

时间：\(O(n + \log V)\)

推广 \(n\) 个离散数的逆元

1. 求前缀积
2. 求总积的逆元
3. 求前缀积的逆元
4. 用前缀积相除得每一位的逆元

要点

• 要求互质，要求互质，要求互质，费马小要求 \(p\) 为质数
• #define int long long
• 不互质时人脑运算
• 模数为质数时可以用费马小求同余方程和不定方程
• 用求法 3 和 求法 4 可以批量求同余方程和不定方程解？

Problem

P1082 [NOIP 2012 提高组] 同余方程

P3811 【模板】模意义下的乘法逆元

P2265 路边的水沟

P5431 【模板】模意义下的乘法逆元 2

P1593 因子和

题解：因子和为 \((1 + p _ 1 ^ 1 + p _ 1 ^ 2 + ... + p _ 1 ^ {b \times k _ 1}) (1 + p _ 2 ^ 1 + p _ 2 ^ 2 + ... + p _ 2 ^ {b \times k _ 2}) ...\) 于是转化为等比数列求和，有公式 \(s_n = \frac{a_1(q ^ n - 1)}{q - 1}\) 于是逆元即可，不互质时人脑运算。

启示：题解都是

P2054 [AHOI2005] 洗牌

题解：找递推方程，发现在模 \(n + 1\) 意义下是一定的，有同余方程 \(2 ^ mp \equiv l \pmod {n + 1}\) 求逆元即可。

启示：递推方程 + 同余方程 = 逆元？