【模板】线性求逆元（洛谷P3367）

Description

　　给定(n),(p)求(1~n)中所有整数在模(p)意义下的乘法逆元。

Input

　　一行(n),(p)

Output

　　(n)行,第(i)行表示(i)在模(p)意义下的逆元。

Solution

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,p,inv[30000000];
int main()
{
	scanf("%d%d",&n,&p);
	inv[1]=1;
	for (int i=2;i<=n;i++) inv[i]=1LL*(p-p/i)*inv[p%i]%p;
	for (int i=1;i<=n;i++) printf("%d
",inv[i]);
	return 0;
}