欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

一个线性求逆元的方法

程序员文章站 2022-06-05 11:28:22
...

其实逆元的线性求法和之前提到的两种筛法没什么关系,我更喜欢称这个做法叫逆元的递推求法。但是考虑到贾志鹏的线性筛PPT里提到了逆元的线性求法,我就在这里也说下吧。

逆元其实不是函数,但是我们可以把它看成函数f(x),逆元(函数)的积性性质也是非常显然的,我就不赘述了。

实际上x和x-p在模p意义下的逆元是相同的,因此我们只需要筛出1...p1的逆元就够了。

我们假设模数p=ki+r,r<i,1<ip

 

ki+r0(modp)

 

两边同时乘上i1r1

 

kr1+i10(modp)

 

 

i1kr1(modp)

 

 

i1pi(pmodi)1(modp)

 

于是我们可以推出i的逆元f(i)=[pif(pmodi)]modp

所以逆元可以直接通过递推的方式求出来。

逆元的线性求法代码:

for(LL i=2;i<MOD;i++)
    rev[i]=(MOD-MOD/i)*rev[MOD%i]%MOD;

 由于加上一个MOD没什么影响,所以正好通过这样我们能得到大于零的结果