求多个乘法逆元（模板）

线性算法

用于求一连串数字对于一个modp的逆元。洛谷P3811

只能用这种方法，别的算法都比这些要求一串要慢。

首先我们有一个,1−1≡1(modp)

然后设 p=k∗i+r,(1<r<i<p) 也就是 k 是 p/i 的商，r 是余数 。

再将这个式子放到(modp)意义下就会得到：

k∗i+r≡0(modp)

然后乘上i−1,r−1就可以得到:

k∗r−1+i−1≡0(modp)i−1≡−k∗r−1(modp)i−1≡−⌊ip​⌋∗(pmodi)−1(modp)

于是，我们就可以从前面推出当前的逆元了。

代码也很短：

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