逆元学习笔记

acdreamer_逆元学习笔记

摘重点：

ksm(a,mod-2)的方法求逆元只适用于mod为质数且 gcd(a,mod)==1

扩展欧几里得算法求逆元只适用于gcd(a,mod)==1

扩展欧几里得算法求逆元

acdreamer的博客里提到一种通用的方法，正确性未知。（然而有b|a的前提呵呵呵呵呵）

但是你会发现费马小定理和扩展欧几里得算法求逆元是有局限性的，它们都会要求

与

互素。实际上我们还有一

种通用的求逆元方法，适合所有情况。公式如下

O(n)求逆元：

其实有些题需要用到

模

的所有逆元，这里

为奇质数。那么如果用快速幂求时间复杂度为

，

如果对于一个1000000级别的素数

，这样做的时间复杂度是很高了。实际上有

的算法，有一个递推式如下

它的推导过程如下，设

，那么

对上式两边同时除

，进一步得到

再把

和

替换掉，最终得到

初始化

，这样就可以通过递推法求出

模奇素数

的所有逆元了。

另外

模

的所有逆元值对应

中所有的数，比如

，那么

对应的逆元是

。