乘法逆元
本文介绍模意义下乘法运算的逆元(Modular Multiplicative Inverse),并介绍如何使用扩展欧几里德算法(Extended Euclidean algorithm)求解乘法逆元。
定义
如果一个线性同余方程
如何求逆元
扩展欧几里得法
实现
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 |
|
扩展欧几里得法和求解 线性同余方程 是一个原理,在这里不展开解释。
快速幂法
证明
因为
所以
所以
然后我们就可以用快速幂来求了。
实现
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 |
|
注意:快速幂法使用了 费马小定理,要求
线性求逆元
求出
如果对于每个数进行单次求解,以上两种方法就显得慢了,很有可能超时,所以下面来讲一下如何线性(
首先,很显然的
证明
对于
其次对于递归情况
两边同时乘
再带入
我们注意到
故我们就可以推出逆元,利用递归的形式,而使用迭代实现:
实现
1 2 3 4 |
|
1 2 3 |
|
使用
另外我们注意到我们没有对 inv[0]
进行定义却可能会使用它:当 inv[p % i]
,也就是 inv[0]
,这是因为当 inv[i]
的值是未定义的。
另外,根据线性求逆元方法的式子:
递归求解
中间优化可以加入一个记忆化来避免多次递归导致的重复,这样求
注意:如果用以上给出的式子递归进行单个数的逆元求解,目前已知的时间复杂度的上界为
线性求任意 n 个数的逆元
上面的方法只能求
首先计算
因为
同理我们可以依次计算出所有的
所以我们就在
实现
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 9 |
|
逆元练习题
本页面最近更新:2024/5/8 20:33:33,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:iamtwz, abc1763613206, buggg-hfc, dkz051, Enter-tainer, Great-designer, Henry-ZHR, hqztrue, hsfzLZH1, ImpleLee, Ir1d, JellyGoat, jifbt, lhhxxxxx, Marcythm, MegaOwIer, Menci, MioChyan, n-WN, ouuan, PeterlitsZo, Phemon, shawlleyw, Siyuan, sshwy, stevebraveman, StudyingFather, thredreams, Tiooo111, Tiphereth-A, WAAutoMaton, Xeonacid, Zhaoyangzhen
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用