其实逆元的线性求法和之前提到的两种筛法没什么关系，我更喜欢称这个做法叫逆元的递推求法。但是考虑到贾志鹏的线性筛PPT里提到了逆元的线性求法，我就在这里也说下吧。
逆元其实不是函数，但是我们可以把它看成函数f(x)，逆元(函数)的积性性质也是非常显然的，我就不赘述了。
实际上x和x-p在模p意义下的逆元是相同的，因此我们只需要筛出1...p−1的逆元就够了。
我们假设模数p=ki+r,r<i,1<ip
则
ki+r≡0(modp)
两边同时乘上i−1r−1：
kr−1+i−1≡0(modp)
i−1≡−kr−1(modp)
i−1≡−⌊pi⌋(pmodi)−1(modp)
于是我们可以推出i的逆元f(i)=[−⌊pi⌋f(pmodi)]modp
所以逆元可以直接通过递推的方式求出来。
逆元的线性求法代码：
for(LL i=2;i<MOD;i++)
rev[i]=(MOD-MOD/i)*rev[MOD%i]%MOD;
由于加上一个MOD没什么影响，所以正好通过这样我们能得到大于零的结果