逆元学习笔记

acdreamer_逆元学习笔记

 

摘重点:

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

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

扩展欧几里得算法求逆元

acdreamer的博客里提到一种通用的方法,正确性未知(然而有b|a的前提呵呵呵呵呵)

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

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

 

O(n)求逆元:

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

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

 

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

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

再把替换掉,最终得到

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

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

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz