逆元学习笔记

acdreamer_逆元学习笔记

摘重点：

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

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

扩展欧几里得算法求逆元

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

但是你会发现费马小定理和扩展欧几里得算法求逆元是有局限性的，它们都会要求与互素。实际上我们还有一

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

O(n)求逆元：

其实有些题需要用到模的所有逆元，这里为奇质数。那么如果用快速幂求时间复杂度为，

如果对于一个1000000级别的素数，这样做的时间复杂度是很高了。实际上有的算法，有一个递推式如下

 

它的推导过程如下，设，那么

对上式两边同时除，进一步得到

再把和替换掉，最终得到

初始化，这样就可以通过递推法求出模奇素数的所有逆元了。

另外模的所有逆元值对应中所有的数，比如，那么对应的逆元是。