乘法逆元
出处说明
本文内容摘自外部资源,为方便学员快速学习相关前置数学知识而整理在一起。内容可能较原文有删减,仅保留本课程所需的前置内容,以便学员快速掌握必备知识。
本文介绍模意义下乘法运算的逆元(Modular Multiplicative Inverse),并介绍如何使用扩展欧几里德算法(Extended Euclidean algorithm)求解乘法逆元。
定义
如果一个线性同余方程
如何求逆元
扩展欧几里得法
扩展欧几里得法和求解 线性同余方程 是一个原理,在这里不展开解释。
线性求逆元
求出
如果对于每个数进行单次求解,以上两种方法就显得慢了,很有可能超时,所以下面来讲一下如何线性(
首先,很显然的
???+ note "证明" 对于
其次对于递归情况
两边同时乘
再带入
我们注意到
故我们就可以推出逆元,利用递归的形式,而使用迭代实现:
使用
另外我们注意到我们没有对 inv[0]
进行定义却可能会使用它:当 inv[p % i]
,也就是 inv[0]
,这是因为当 inv[i]
的值是未定义的。
另外,根据线性求逆元方法的式子:
递归求解
中间优化可以加入一个记忆化来避免多次递归导致的重复,这样求
注意:如果用以上给出的式子递归进行单个数的逆元求解,目前已知的时间复杂度的上界为
线性求任意 n 个数的逆元
上面的方法只能求
首先计算
因为
同理我们可以依次计算出所有的
所以我们就在