专栏文章

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

PPCSJZ
P3811题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip9cevp
此快照首次捕获于
2025/12/03 08:17
3 个月前
此快照最后确认于
2025/12/03 08:17
3 个月前
查看原文

递推法求乘法逆元

这一点非常的重要！
应用：求 1∼n1 \sim n 的所有乘法逆元。
时间复杂度：O(n)O(n)。
首先，我们要知道 1−1≡1(modp)1^{-1} \equiv 1 \pmod p，因为：显然，在 pp 下，11 是 11 的乘法逆元。
其次，对于递归情况 i−1i^{-1}，我们设 k=⌊pi⌋,j=p mod ik=\left \lfloor \frac{p}{i} \right \rfloor, j = p \bmod i，则有 p=ki+jp = ki + j。
所以，在模 pp 意义下，ki+j≡0(modp)ki+j \equiv 0 \pmod p。
此时，左右两边同时乘以 i−1×j−1i^{-1} \times j^{-1}，得：
ki×i−1×j−1+j×i−1×j−1≡0(modp)ki \times i^{-1} \times j^{-1} + j \times i^{-1} \times j^{-1} \equiv 0 \pmod p
kj−1+i−1≡0(modp)kj^{-1}+i^{-1} \equiv 0 \pmod p
i−1≡−kj−1(modp)i^-1 \equiv -kj^{-1} \pmod p
再带入 j=p mod i,k=⌊pi⌋j = p \bmod i, k = \left \lfloor \frac{p}{i} \right \rfloor，得：
i−1≡−⌊pi⌋(p mod i)−1(modp)i^{-1} \equiv -\left \lfloor \frac{p}{i} \right \rfloor (p \bmod i)^{-1} \pmod p
i−1≡(p−pi)(p mod i)−1(modp)i^{-1} \equiv (p-\frac{p}{i}) (p \bmod i)^{-1} \pmod p
注意， p mod i<ip \bmod i < i，又因为在递推的过程中，我们已经求出了所有小于 ii 的在模 pp 意义下的乘法逆元，可表示为 q−1,q<iq^{-1}, q<i。从 pi\frac{p}{i} 改成p−pip - \frac{p}{i} 是因为我们的运算符是同余，系数可以随便改。

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...