逆元NOIP

💡 核心思想

在模意义下，$a$ 的逆元 $a^{-1}$ 满足 $a \cdot a^{-1} \equiv 1 \pmod{p}$。逆元的作用是在模意义下做"除法"：$a/b \equiv a \cdot b^{-1} \pmod{p}$。求法：费马小定理（$p$ 为质数时）或扩展欧几里得。

🎯 直觉理解

模逆元解决"模意义下的除法"：模质数 M 下，a 的逆元 $a^{-1}$ 满足 $a imes a^{-1}equiv 1pmod M$，于是除法 $b/a$ 变成乘 $b imes a^{-1}$。

为什么需要：模运算下不能直接除（$b/a mod M$ 不等于 $(b mod M)/(a mod M)$），组合数计算、概率取模都必须用逆元。

求法二选一：M 是质数时用费马小定理 $a^{M-1}equiv 1$，所以 $a^{-1}=a^{M-2}$（快速幂算）；M 不保证质数时用扩展欧几里得解 $ax+My=1$。求 1 到 n 所有逆元有 $O(n)$ 线性递推公式。费马小定理版最好记，先掌握它。

📝 算法流程

1. 费马小定理：$a^{p-2} \mod p$（$p$ 为质数）
2. 扩展欧几里得：求解 $ax \equiv 1 \pmod{p}$
3. 线性递推：$inv[i] = -(p/i) \times inv[p \mod i] \mod p$

$$a^{-1} \equiv a^{p-2} \pmod{p} \text{（费马小定理，} p \text{ 为质数）}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
typedef long long ll;
ll qpow(ll a, ll n, ll mod) { ll ans=1; a%=mod; while(n){if(n&1)ans=ans*a%mod; a=a*a%mod; n>>=1;} return ans; }
int main() {
    int n, p; cin >> n >> p;
    // 方法1：费马小定理（p 为质数）
    for (int i = 1; i <= n; i++)
        cout << qpow(i, p-2, p) << "\n";
    // 方法2：线性递推
    vector inv(n+1); inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = (p - p/i) * inv[p%i] % p;
    return 0;
}

⚠️ 常见坑点

📚 相关题目