乘法逆元的几种计算方法

Bertha 。 2022-03-10 13:28 382阅读 0赞

转载自：[https://blog.csdn.net/rain722/article/details/53170288][https_blog.csdn.net_rain722_article_details_53170288]

乘法逆元是数论中重要的内容，也是 ACM 中常用到的数论算法之一。所以，如何高效的求出乘法逆元是一个值得研究的问题。

这里我们只讨论当模数为素数的情况，因为如果模数不为素数，则不一定每个数都有逆元。

定义  
在  mod p的意义下我们把 xx 的乘法逆元写作x ^ \{-1\}*x*−1。

乘法逆元有如下的性质：

![20161115133003092][]

乘法逆元的一大应用是模意义下的除法，除法在模意义下并不是封闭的，但我们可以根据上述公式，将其转化为乘法。

![20161115133024514][]

## **费马小定理** ##

![20161115133123795][]

要求 pp为素数。

上述公式可变形为

![20161115133143578][]

由乘法逆元的定义，a ^ \{p - 2\}ap−2  即为 aa 的乘法逆元。

使用快速幂计算  a ^ \{p - 2\}ap−2，总时间复杂度为 O(\\log a)O(loga)。

代码  
inline int pow(const int n, const int k) \{  
    long long ans = 1;  
    for (long long num = n, t = k; t; num = num \* num % MOD, t >>= 1) if (t & 1) ans = ans \* num % MOD;  
    return ans;  
\}  
inline int inv(const int num) \{  
    return pow(num, MOD - 2);  
\}

## **扩展欧几里得** ##

扩展欧几里得（EXGCD）算法可以在 O(\\log \\max(a, b))O(logmax(a,b)) 的时间内求出关于 xx、yy 的方程

![20161115133307705][]  
的一组整数解

当 bb为素数时，gcd(a, b) =1，此时有

![20161115133427062][]

时间复杂度为 O(\\log a)O(loga)。

代码  
void exgcd(const int a, const int b, int &g, int &x, int &y) \{  
    if (!b) g = a, x = 1, y = 0;  
    else exgcd(b, a % b, g, y, x), y -= x \* (a / b);  
\}  
inline int inv(const int num) \{  
    int g, x, y;  
    exgcd(num, MOD, g, x, y);  
    return ((x % MOD) + MOD) % MOD;  
\}

##    **递推法** ##

![20161115133621303][]  
代码  
inv\[1\] = 1;  
for (int i = 2; i <= MAXN; i++) inv\[i\] = ((-(MOD / i) \* inv\[MOD % i\]) % MOD + MOD) % MOD;

下面是ACdreamers关于递推求解逆元的推导过程（个人觉得他的更好）

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

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

![20140613123955765][]

它的推导过程如下，设![20140613124932968][]，那么

![20140613125025984][]

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

![20140613125208000][]

再把 t 和 k 替换掉，最终得到

![20140613123955765][]

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

另外![20140613122746828][]模 p 的所有逆元值对应![20140613122746828][]中所有的数，比如![20140613125913078][]，那么![20140613130144843][]对应的逆元是![20140613130219921][]。

[https_blog.csdn.net_rain722_article_details_53170288]: https://blog.csdn.net/rain722/article/details/53170288
[20161115133003092]: /images/20220310/1007e8006f1d44b29e966b0862c5aaf7.png
[20161115133024514]: /images/20220310/74242040c2d34cfa8182132c640738eb.png
[20161115133123795]: /images/20220310/545586e3505f4367b364f0f6a0658ed1.png
[20161115133143578]: /images/20220310/79c6910b394948f395b7448dea16e5eb.png
[20161115133307705]: /images/20220310/2b64e65b47fb4555b4879dfd48584899.png
[20161115133427062]: /images/20220310/478e78e6ab3543f9a731152f39b47d62.png
[20161115133621303]: /images/20220310/56eae1083f164a669dd9647b2bb623a8.png
[20140613123955765]: /images/20220310/7e5cd9d52d1b4b4bb6e1b7cd173c985b.png
[20140613124932968]: /images/20220310/dd8535db98624751ae5d1d7bcf8854ce.png
[20140613125025984]: /images/20220310/662635bd355a4a88bc2d7a108c0f4517.png
[20140613125208000]: /images/20220310/01028bcb3a86449a9037240254d37d08.png
[20140613125520578]: https://img-blog.csdn.net/20140613125520578
[20140613122746828]: /images/20220310/41e0adf9a46f4c90830c9f11929df72e.png
[20140613125913078]: https://img-blog.csdn.net/20140613125913078
[20140613130144843]: https://img-blog.csdn.net/20140613130144843
[20140613130219921]: /images/20220310/47ae002f28824cfebe8ebeb7de6bdf47.png