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