[模板]线性求逆元

洛谷：P3811 【模板】乘法逆元 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

推导过程

保证 模数P 为一个质数。

代码 / code

/*Copyright (C) Eriktse 2022*/
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 3e6 + 9;

int inv[maxn];

void initInv(int N, int P,int a[])//a[]用于接收并操作inv数组 
{
	a[0] = a[1] = 1;//初始化 
	for(int i = 2;i <= N; ++ i)a[i] = (P - P / i) * a[P % i] % P;
}

signed main()
{
	int N, P;cin >> N >> P;
	initInv(N, P, inv);
	for(int i = 1;i <= N; ++ i)printf("%lld\n",inv[i]);
	return 0;
}