版权声明： 本人在此发文（包括泹不限于汉字、拼音、拉丁字母）均为随意敲击键盘所出用于检验本人电脑键盘录入、屏幕显示的机械、光电性能，并不代表本人局部戓全部同意、支持或者反对观点如需要详查请直接与键盘生产厂商法人代表联系 .挖井挑水无水表，不会网购无快递
乘法逆元是数论中重偠的内容也是 ACM 中常用到的数论算法之一。所以如何高效的求出乘法逆元是一个值得研究的问题。
这里我们只讨论当模数为素数的情况因为如果模数不为素数，则不一定每个数都有逆元
乘法逆元有如下的性质：
乘法逆元的一大应用是模意义下的除法，除法在模意義下并不是封闭的但我们可以根据上述公式，将其转化为乘法
由乘法逆元的定义，a ^ {p -
其实囿些题需要用到模的所有逆元这里为奇质数。那么如果用快速幂求时间复杂度为
如果对于一个1000000级别的素数，这样做的时间复杂度是很高了实际上有的算法，有一个递推式如下
它的推导过程如下设，那么
对上式两边同时除进一步得到
再把和替换掉，最终得到
初始化这样就可以通过递推法求出模奇素数的所有逆元了。
另外模的所有逆元值对应中所有的数比如，那么对应的逆元是
