乘法逆元
本文介绍模意义下乘法运算的逆元(Modular Multiplicative Inverse),并介绍如何使用扩展欧几里德算法(Extended Euclidean algorithm)求解乘法逆元。
定义
线性同余方程
是一个原理,在这里不展开解释。
快速幂法
费马小定理
);
所以
。
然后我们就可以用快速幂来求了。
实现
注意:快速幂法使用了
费马小定理
,要求
是一个素数;而扩展欧几里得法只要求
。
线性求逆元
线性同余方程
中指出,如果
与
不互素时不存在相应的逆元(当一般而言我们会使用一个大素数,比如
来确保它有着有效的逆元)。因此需要指出的是:如果没有相应的逆元的时候,
inv[i]
的值是未定义的。
另外,根据线性求逆元方法的式子:
递归求解
, 直到
返回
。
中间优化可以加入一个记忆化来避免多次递归导致的重复,这样求
中所有数的逆元的时间复杂度仍是
。
注意
:如果用以上给出的式子递归进行单个数的逆元求解,目前已知的时间复杂度的上界为
,具体请看
知乎讨论
。算法竞赛中更好地求单个数的逆元的方法有扩展欧几里得法和快速幂法。
线性求任意 n 个数的逆元