信奥赛C++提高组csp-s之数论基础专题课：从同余到分数模运算6(案例实践：乘法逆元)

信奥赛C++提高组csp-s之数论基础专题课：从同余到分数模运算6(案例实践：乘法逆元)

课程目标

第三部分：案例实战（乘法逆元）

研究案例：P3811 模意义下的乘法逆元

题目描述

给定正整数

n

,

p

n,p

n,p，求

[

1

,

n

]

[1,n]

[1,n] 中所有整数在模

p

p

p 意义下的乘法逆元。

a

a

a 模

p

p

p 的乘法逆元定义为

a

x

≡

1

(

m

o

d

p

)

ax\\equiv1\\pmod p

ax≡1(modp) 的解。

输入格式

一行两个正整数

n

,

p

n,p

n,p。

输出格式

输出

n

n

n 行，其中第

i

i

i 行表示

i

i

i 在模

p

p

p 下的乘法逆元。

输入输出样例 1

输入 1

10 13

输出 1

1
7
9
10
8
11
2
5
3
4

说明/提示

所有数据满足

1

≤

n

≤

3

×

10

6

1 \\leq n \\leq 3 \\times 10 ^ 6

1≤n≤3×106，

n

<

p

<

20000528

n < p < 20000528

n<p<20000528。

输入保证

p

p

p 为质数。

思路分析

本题要求计算

1

1

1 到

n

n

n 每个数在模素数

p

p

p 下的乘法逆元。 已知

p

p

p 为质数且

n

<

p

n < p

n<p，因此可以使用 线性递推 在

O

(

n

)

O(n)

O(n) 时间内求出所有逆元。

递推公式（适用于质数模数

p

p

p）：

i

n

v

[

i

]

=

(

p

−

⌊

p

i

⌋

)

⋅

i

n

v

[

p
 

m

o

d

i

]
 

m

o

d

p

\\mathrm{inv}[i] = \\left(p – \\left\\lfloor \\frac{p}{i} \\right\\rfloor\\right) \\cdot \\mathrm{inv}[p \\bmod i] \\bmod p

inv[i]=(p−⌊ip​⌋)⋅inv[pmodi]modp 初始条件：

i

n

v

[

1

]

=

1

\\mathrm{inv}[1] = 1

inv[1]=1

推导过程 对 p 除以 i 做带余除法：p=i⋅q+r，其中 q=⌊p/i⌋，r=p mod i（0<r<i）。 在模 p意义下，有

iq + r ≡ 0 (mod p) ⇒ r ≡ −iq (mod p)

由于 p 是质数且 r < p，r 与 p互质，故 r存在逆元 inv[r]。两边乘以 inv[r] 得

1

≡

−

i

q

⋅

i

n

v

[

r

]

(

m

o

d

p

)

1≡−iq⋅inv[r] (modp)

1≡−iq⋅inv[r](modp)

此式表明 −q⋅inv[r] 与 i 的乘积模 p 等于 1，因此它就是 i 的逆元：

i

n

v

[

i

]

≡

−

q

⋅

i

n

v

[

r

]

(

m

o

d

p

)

inv[i]≡−q⋅inv[r](modp)

inv[i]≡−q⋅inv[r](modp)

将负系数化为正数（模 p 下 −q ≡ p − q），并代入 q = ⌊ p/i ⌋，r = p mod i 即得递推公式。

递推可行性 因为 r = p  mod  i < i，计算 inv[i] 时所需的 inv[r] 已经在前面的步骤中求出，故可从 i=1 开始顺序递推，时间复杂度 O(n)。

注意事项：

• 递推中乘法可能溢出 32 位整数（$p$
• $n$

代码实现

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

const int MAXN = 3000010;
int inv[MAXN]; // 存储逆元的数组

int main() {
int n, p;
scanf("%d%d", &n, &p); // 输入 n 和模数 p

inv[1] = 1; // 1 的逆元是 1
for (int i = 2; i <= n; ++i) {
// 递推公式：inv[i] = (p – p/i) * inv[p % i] % p
// 使用 1ll 将乘法转换为 long long 防止溢出
inv[i] = (p – (p / i)) * 1ll * inv[p % i] % p;
}

// 输出结果
for (int i = 1; i <= n; ++i) {
printf("%d\\n", inv[i]);
}
return 0;
}

功能分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》： https://blog.csdn.net/weixin_66461496/category_13113932.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"########## 一站式掌握信奥赛知识! ##########";
cout<<"############# 冲刺信奥赛拿奖! #############";
cout<<"###### 课程购买后永久学习，不受限制! ######";
return 0;
}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划： https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL： https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践： https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新） https://blog.csdn.net/weixin_66461496/category_13125089.html

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13117178.html

4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}