隐藏
乘法逆元技巧总结 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

乘法逆元技巧总结

乘法逆元

对于式子:

我们称$a’$是$a$在模$p$意义下的乘法逆元,记作$a^{-1}$。
乘法逆元在数论中有重要的意义。
其用途和倒数类似,若要在模$p$意义下将$a$除以$b$,不能直接$a/b$,因为除法是不满足模运算的,此时我们需要转为乘法:$a\cdot b^{-1}$。

如何求出一个数的乘法逆元

若模数$p$是一个素数,则根据费马小定理:

因此$a\cdot a^{p-2}\equiv1\pmod p$
因此$a^{-1}\equiv a^{p-2}\pmod p$

更一般地,若$p$是任意数,$a$并不一定存在乘法逆元。
若$\gcd(a,p)=1$,根据欧拉定理:

因此$a^{-1}\equiv a^{\varphi(p)-1}\pmod p$

求出$[1,n]$所有数的乘法逆元

在上一段我们讲了如何求出一个数的乘法逆元,但若要求出$[1,n]$所有数的乘法逆元,上述算法时间复杂度为$O(n\log n)$,在一些组合计数问题中容易被卡常数,因此本处介绍一种线性求逆元的方法。

要求:$p$是质数

设$p=ka+b$,其中$b\lt a,1\lt a\lt p$。

等式两边同时乘上$a^{-1}b^{-1}$,得到:

递推一遍即可得出答案。

1
2
inv[1]=1;
for(int i=2; i<=n; i++)inv[i]=(p-p/i)*inv[p%i]%p;

姥爷们赏瓶冰阔落吧~