【ybt高效进阶6-3-3】线性求逆元(数学)
线性求逆元
题目链接:ybt高效进阶6-3-3
题目大意
给你 n,p,要你求 1~n 每个数在模 p 意义下的逆元。
思路
线性求逆元的公式就是:
i
n
v
i
=
(
(
p
−
p
/
i
∗
i
n
v
p
m
o
d
i
)
m
o
d
p
+
p
)
m
o
d
p
inv_i=((p-p/i*inv_{p\bmod i})\bmod p+p)\bmod p
invi=((p−p/i∗invpmodi)modp+p)modp
这里给一下证明:
因为是线性,所以假设我们求
i
i
i,那
1
∼
i
−
1
1\sim i-1
1∼i−1 的我们都求出来了。
那
p
p
p 可以表示成
⌊
p
i
⌋
∗
i
+
r
(
0
⩽
r
<
i
)
\left\lfloor\dfrac{p}{i}\right\rfloor*i+r(0\leqslant r<i)
⌊ip⌋∗i+r(0⩽r<i),所以就有
⌊
p
i
⌋
∗
i
+
r
≡
0
(
m
o
d
p
)
\left\lfloor\dfrac{p}{i}\right\rfloor*i+r\equiv0(\bmod\ p)
⌊ip⌋∗i+r≡0(mod p)
然后两边都乘
i
n
v
i
∗
i
n
v
r
inv_i*inv_r
invi∗invr,就有
⌊
p
i
⌋
∗
i
n
v
r
+
i
n
v
i
≡
0
(
m
o
d
p
)
\left\lfloor\dfrac{p}{i}\right\rfloor*inv_r+inv_i\equiv0(\bmod\ p)
⌊ip⌋∗invr+invi≡0(mod p)
i
n
v
i
≡
−
⌊
p
i
⌋
∗
i
n
v
r
(
m
o
d
p
)
inv_i\equiv-\left\lfloor\dfrac{p}{i}\right\rfloor*inv_r(\bmod\ p)
invi≡−⌊ip⌋∗invr(mod p)
然后由于 ( 0 ⩽ r < i ) (0\leqslant r<i) (0⩽r<i), i n v r inv_r invr 是已知的,所以就得出了 i n v i inv_i invi。
代码
#include<cstdio>
using namespace std;
int n, p, inv[3000001];
int main() {
scanf("%d %d", &n, &p);
inv[1] = 1;
for (int i = 2; i <= n; i++)//不开 long long 见祖宗
inv[i] = ((1ll * p - 1ll * p / i * inv[p % i]) % p + p) % p;
for (int i = 1; i <= n; i++) printf("%d\n", inv[i]);
return 0;
}
相关文章
- 云数据库 GaussDB(for Influx) 解密第十一期:让智能电网中时序数据处理更高效
- 2021Android目前最稳定和高效的UI适配方案!大厂面试题汇总
- Golang:Gomail一个简单高效的电子邮件发送包
- 高效判断远程图片是否存在
- 如何防止删库跑路?运维堡垒机高效安全运维设计与实践落地
- .NET高性能编程 - C#如何安全、高效地玩转任何种类的内存之Span的本质(一)。
- 我的渗透测试路,如何入门网络安全最高效?附面试经验
- 如何建立高效推送通知
- 高效线程池之无锁化实现(Linux C)
- 【jzoj 1326】【luogu 1886】【ybt高效进阶5-6-1】Window & 滑动窗口 /【模板】单调队列
- 【ybtoj高效进阶 21170】投篮训练(贪心)(线段树)(构造)
- 【ybtoj高效进阶 21281】矩阵逆转(模拟)
- 【ybt高效进阶6-1-1】序列的第k个数(快速幂)
- 【ybt高效进阶2-2-3】【luogu P2601】对称正方形
- 【ybt高效进阶1-2-3】【luogu P2859】畜栏预定 / Stall Reservations S
- 【ybtoj高效进阶 21277】逆序对数(数学)(DP)
- 【ybtoj高效进阶 21276】异或求和(数学)
- 【ybt高效进阶6-4-3】【luogu P2480】古代猪文(数学)(EXCRT / CRT)(Lucas定理)(欧拉定理)
- 【ybt高效进阶6-4-2】方案统计(卢卡斯定理)
- 【ybt高效进阶6-3-4】中国剩余定理(数学)
- 【ybt高效进阶6-3-2】约数之和(逆元)(数学)
- 【ybt高效进阶6-2-2】质数距离(素数筛选法)
- 【ybtoj高效进阶 21169】毁灭计划(分类讨论)(树形DP)
- 【ybtoj高效进阶 21268】数塔路径(DP)
- 【ybtoj高效进阶 21266】历经磨难(单调队列优化DP)
- 【ybt高效进阶4-2-3】【luogu UVA12983】严格上升子序列数 / The Battle of Chibi
- 【ybt高效进阶5-3-1】B数计数(数位DP)
- 【ybt高效进阶4-2-4】【POJ 3468】区间修改区间查询 / A Simple Problem with Integers
- 【ybt高效进阶4-2-5】单点修改区间查询
- 【ybt高效进阶3-2-3】公路建设
- 【ybtoj高效进阶 21270】三只企鹅(树链剖分)(线段树)
- 【ybtoj高效进阶 21252】逛动物园(线段树)(dfs)
- 【ybtoj高效进阶 21185】树上询问(LCT)
- 【ybt高效进阶1-3-2】防具布置
- 【ybt高效进阶1-5-6】【HDU 3085】逃离噩梦 / Nightmare Ⅱ
- 【ybt高效进阶2-5-4】屏蔽词删除
- 学会写作:自我进阶的高效方法
- 60+ 实用 React 工具库,助力你高效开发
- 简单学JAVA-Java高效学习路线-自学必读