线性求乘法逆元

用于求一连串数字对于一个 mod p的逆元。如果只是求一个数的逆元建议使用费马小定理或扩展欧几里德定理。
线性算法求逆元的原理：
已知， (1/1)≡1 (mod p) , 设 p=k∗i+r,(1<r<i<p) ， 即k 是 p/i的商 ， r 是 p/i 的余数。
即 k∗i+r≡0 (mod p)。 ≡左右两边同时乘上(1/i)*(1/r) ， 即 k * (1/r) + (1/i) ≡0 (modp) 。
移项可得 ， (1/i) ≡ - k * (1/r) (mod p) 。
即 （1/i） ≡ (-p/i) * (1/(p%i)) (mod p) 。
即 inv[i] ≡ （long long）(-p/i + p) * inv[p%i] (mod p) 。

源码如下所示：

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 3e6+10;
int inv[maxn];

int main(){
	int n,p;
	cin >> n >> p;
	inv[1] = 1;
	cout << inv[1] << endl;
	for(int i = 2;i <= n;i++){
		inv[i] = (long long)(-p/i+p)*inv[p%i]%p;
		printf("%d\n",inv[i]);
	}
	return 0;
}