[C++知识库]P3811 【模板】乘法逆元（C++）

P3811 【模板】乘法逆元

递推公式，不做证明了，我也不会

inv [ i ] = (mod - mod/i)*inv[ mod%i ] %mod;

注意这题用cout就会TLE，但是用printf不会

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#include<vector>
#include <algorithm>
#include<string.h>
#include<math.h>
#define llu unsigned long long
typedef long long  ll;
using namespace std;

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