逆元,即对给定(a,p (a perp p)),求(x)使得(ax equiv 1 (mod p))
逆元可以看做(a)在模(p)意义下的(a^{-1})。因此,在模(p)意义下,可以用乘(a)的逆元的方式来代替除以(a)操作
求单个数的逆元
费马小定理求逆元
当(p)是质数且(aperp p)时 $$a^{p-1}equiv1quad (mod p) $$
方程两边同时乘(a^{-1}),可以发现$$a^{-1}equiv a ^{p-2}quad(mod p)$$
可以直接快速幂求 传送门
欧拉定理求逆元
欧拉定理可以适用于满足(aperp p)的情况 $$a^{varphi(p)}equiv 1quad (mod p) $$
同理可得$$a^{-1}equiv a^{varphi(p)-1} quad (mod p) $$
现在的问题变成了,如何求欧拉函数?
1.线性筛(O(p))求
适用于多个模数的情况 传送门
如果是单一模数怎么办呢?有更高效的做法
2.(O(sqrt{p}))做法
[varphi(p)=pprodlimits_{i}(1-frac1i)
]
其中,(i)是(p)的所有质因子
#define LL long long
LL get_phi(LL n)
{
LL sum = n;
for (LL i = 1; i * i <= n; ++i)
if (n % i == 0)
{
sum -= sum / i;
while (n % i == 0)
n /= i;
}
if (n > 1)
sum -= sum / n;
return sum;
}
exgcd求逆元
exgcd可以求解方程组(ax+by=c)的解,而求(a)在模(p)下的逆元可以转化为求(ax+py=1)的解
求多个数的逆元
线性求1~n的逆元
令(p=ki+r,k=lfloorfrac pi floor. r=p mod i)
则有(ki+r equiv 0quad (mod p)),乘(i^{-1},r^{-1})可得(kr^{-1}+i^{-1}equiv 0quad (mod p))
所以(i^{-1}=-r^{-1}lfloorfrac pi floor)
显然可以递推求解
线性求n个数的逆元
先预处理出这n个数的前缀积(sum_i),然后求出这n个数积的逆元(suminv_n),那么(suminv_{i-1}=suminv_i*a_i),(inv_i=suminv_{i}*sum_{i-1})。