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

PCSJZ · 2025-05-19 12:25:45 · 题解

递推法求乘法逆元

这一点非常的重要！

应用：求 1 \sim n 的所有乘法逆元。

时间复杂度：O(n)。

首先，我们要知道 1^{-1} \equiv 1 \pmod p，因为：显然，在 p 下，1 是 1 的乘法逆元。

其次，对于递归情况 i^{-1}，我们设 k=\left \lfloor \frac{p}{i} \right \rfloor, j = p \bmod i，则有 p = ki + j。

所以，在模 p 意义下，ki+j \equiv 0 \pmod p。

此时，左右两边同时乘以 i^{-1} \times j^{-1}，得：

再带入 j = p \bmod i, k = \left \lfloor \frac{p}{i} \right \rfloor，得：

注意， p \bmod i < i，又因为在递推的过程中，我们已经求出了所有小于 i 的在模 p 意义下的乘法逆元，可表示为 q^{-1}, q<i。从 \frac{p}{i} 改成p - \frac{p}{i} 是因为我们的运算符是同余，系数可以随便改。

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long
ll n, p, inv[3000006];

signed main() {
    cin >> n >> p;
    for (int i = 1; i <= n; i++) {
        if (i == 1) inv[i] = 1;
        else inv[i] = (long long)(p - p / i) * inv[p % i] % p; 
    }
    for (int i = 1; i <= n; i++) 
        cout << inv[i] << "\n";
    return 0;
}