摘重点:
ksm(a,mod-2)的方法求逆元只适用于mod为质数且 gcd(a,mod)==1
扩展欧几里得算法求逆元只适用于gcd(a,mod)==1
acdreamer的博客里提到一种通用的方法,正确性未知。(然而有b|a的前提呵呵呵呵呵)
但是你会发现费马小定理和扩展欧几里得算法求逆元是有局限性的,它们都会要求
与
互素。实际上我们还有一
种通用的求逆元方法,适合所有情况。公式如下
O(n)求逆元:
其实有些题需要用到
模
的所有逆元,这里
为奇质数。那么如果用快速幂求时间复杂度为
,
如果对于一个1000000级别的素数
,这样做的时间复杂度是很高了。实际上有
的算法,有一个递推式如下
它的推导过程如下,设
,那么
对上式两边同时除
,进一步得到
再把
和
替换掉,最终得到
初始化
,这样就可以通过递推法求出
模奇素数
的所有逆元了。
另外
模
的所有逆元值对应
中所有的数,比如
,那么
对应的逆元是
。
说点什么
您将是第一位评论人!