逆元CSP-S

💡 核心思想

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

🎯 直觉理解

在普通算术中，除以 $b$ 就是乘以 $1/b$。在模算术中也有类似的概念——"模 $p$ 意义下的 $1/b$"就是 $b$ 的逆元。它满足"乘以它等于除以 $b$ 的效果"（在模 $p$ 下）。

📝 算法流程

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 <bits/stdc++.h>
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<ll> inv(n+1); inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = (p - p/i) * inv[p%i] % p;
    return 0;
}

⚠️ 常见坑点

📚 相关题目