线性求逆元

$$我们有一个质数p$$
$$\forall i\in Z,def\ q_{i}=[\frac{p}{i}],r_{i}=p\%i\ st:\ p = iq_{i}+r_{i} \ (1)$$
$$def\ i^{-1}*i≡1\ (mod\ p)$$
$$(1)*i^{-1}$$
$$=>p*i^{-1}≡q_{i}+r_{i}*i^{-1}\ (mod\ p)$$
$$∵(p*i^{-1})\%p≡0\ (mod\ p)$$
$$∴r_{i}*i^{-1}≡-q_{i}\ (mod\ p)$$
$$i^{-1}≡-q_{i}*r_{i}^{-1}\ (mod\ p)$$
$$i^{-1}≡(p-[\frac{p}{i}])*(p\%i)^{-1}\ (mod\ p)$$
代码非常简短：

#include<iostream>
#include<cstdio>
int MOD;
int inv[1000005],n;
int main(){
	scanf("%d%d",&n,&MOD);
	inv[1]=1;
	for(int i=2;i<=n;++i){
		inv[i]=(MOD-(MOD/i))*inv[MOD%i]%MOD;
	}
	for(int i=1;i<=n;++i){
		printf("%d ",inv[i]); 
	}
}