逆元 - Hardy's Blog

线性求 $1$ 到 $n$ 在模 $p$ 意义下的乘法逆元（保证 $p$ 为质数且 $p > n$ ），使用的是线性递推递推公式，时间复杂度为 $O (n)$ 。

递推公式推导

设模数为 $p$ ，当前要求逆元的数为 $i$ 。令：

p = k \cdot i + r (k = ⌊ p / i ⌋, r = p mod i)

在模 $p$ 意义下，有：

k \cdot i + r \equiv 0 (mod p)

两边同乘 $i^{- 1} \cdot r^{- 1}$ ：

k \cdot r^{- 1} + i^{- 1} \equiv 0 (mod p)

移项可得：

i^{- 1} \equiv - k \cdot r^{- 1} (mod p)

将 $k = ⌊ p / i ⌋$ 和 $r = p mod i$ 代回：

i^{- 1} \equiv - ⌊ p / i ⌋ \cdot (p mod i)^{- 1} (mod p)

为了保证结果在 $[0, p - 1]$ 范围内，加上 $p$ 取模：

in v [i] = (p - ⌊ p / i ⌋) \cdot in v [p mod i] mod p

由于 $p mod i < i$ ，在计算 $in v [i]$ 时， $in v [p mod i]$ 已经求出，因此可以直接 $O (1)$ 递推。

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 3e6 + 5;
long long inv[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, p;
    cin >> n >> p;

    inv[1] = 1;
    for (int i = 2; i <= n; i++) {
        inv[i] = (long long)(p - p / i) * inv[p % i] % p;
    }

    for (int i = 1; i <= n; i++) {
        cout << inv[i] << "\n";
    }

    return 0;
}