算法笔记:乘法逆元
1.乘法逆元的引入
在模运算中,存在下述性质
需要注意的是,结果可能会出现负数,若只需要正数概念下的模,需对结果使用下述变化
可见该性质对于加法、减法、乘法均成立,但在除法运算中
就算在保证整除的情况下也不一定成立
那么我们该如何解决上述问题,使我们能够在除法运算中也使用模运算的性质呢?
可以注意到,乘法与除法为互逆运算,便考虑将除法转化为乘法,找到
若
2.乘法逆元的性质
现有下述等式成立
两等式两边同乘
整理得
因此,我们只要找到满足
就可以得到
那么
一定存在吗?
当
由
设
因为我们是在整数范围内讨论的逆元概念,所以我们可以推出
而且,上述步骤均可逆,因此乘法逆元存在当且仅当
3.乘法逆元的求解
(1) 利用费马小定理求解
由费马小定理得,当
取
1 | using LL = long long; |
(2) 利用扩展欧几里得算法求解
扩展欧几里得算法可以得出
由于
1 | using LL = long long; |
4.乘法逆元的扩展——线性求逆元
如何求出
依次在模 意义下的逆元?
保证为质数,且
对于
在模
由上述推导出的递推式得,若
由于
注意到,若按等式处理,所得
的值为负数,需进行下述处理
1 | const int maxn = 1e5 + 5; |
- Title: 算法笔记:乘法逆元
- Author: Ginkgo
- Created at : 2024-04-21 16:11:24
- Updated at : 2026-04-26 21:33:17
- Link: https://g1nkgo7.github.io/2024/04/21/算法笔记-逆元/
- License: This work is licensed under CC BY-NC-SA 4.0.
Comments