首页 > 代码库 > 逆元以及线性逆元求法(转)

逆元以及线性逆元求法(转)

对于一个数a,如果a*a^-1=1(modp),那么a^-1是a对于p的逆元

在除法中,除以一个数等于乘上这个数的逆元,即x/y=x*y^-1(modp)

求单个逆元可以用费尔马小定理

对于质数p,a^(p-1)=1(modp),那么a^(p-2)*a=a^(p-1)=1(modp),所以a^-1=a^(p-2),用快速幂求即可

但对于一堆数,例如1~n一一求逆元,用快速幂是O(nlogn)的,若n达到1e7会爆炸,所以需要线性求逆元的方法

 

假设当前要求数i的逆元,且1~i-1的逆元都已经求好了,设模数p为质数

p可以表示为p=k*i+r的形式,其中k相当于除数,i相当于商,r相当于余数

那么k*i+r=0(mod p)这是显然的

模等式两边同时乘以i^-1*r^-1,因为i*i^-1=1(modp),所以等式变成了k*r^-1+i^-1=0(mod p)

移项,得i^-1=-k*r^-1

这其中,k是除数(下取整),相当于p/i,r是余数,相当于p%i

p%i一定小于i,而因为p是质数,所以p%i!=0

1~i-1的所有数的逆元我们都是知道的,以inv[]表示

那么我们就有了inv[i]的递推式:inv[i]=-(p/i)*inv[p%i]=p-((p/i)*inv[p%i])%p

其中,1^-1=1

于是我们就有了线性的逆元求法

逆元以及线性逆元求法(转)