这道题中：P3811 【模板】乘法逆元 - 洛谷

要求模 $p$ 意义下 $1$ 至 $n$ 所有整数的逆元，我们可以采用以下方法：

假设我们现在要求 $i^{-1}$ ： 设 $p=qi+r$ ，其中 $q$ 和 $r$ 为整数，即为 $p$ 除 $i$ 的商和余数。有 $q=\lfloor\frac{p}{i}\rfloor$ ，$r=p\ \%\ i$ 。 显然有

同余式两边同乘 $i^{-1}r^{-1}$：

移项，再代入：

由于 $p\ \%\ i<i$ ，我们肯定先前求过，用一个 $\mathtt{Inv[]}$ 数组来记录每个数的逆元，递推时直接检索即可。 同时我们要保证同余式右侧大于零，按照[[EXGCD]]中求不定方程最小非负整数解的方法即可：

递推起点是 $\mathtt{Inv[}\ 1\ \mathtt{]}=1$ ，当然循环要从 $2$ 开始，题目保证了 $p>n$ 且为质数，故无需考虑 $p\ \%\ i=0$ 的情况。

时间复杂度为 $\mathrm{O}(n)$

参考代码：

#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
//---//
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

typedef unsigned int u;
typedef long long ll;
typedef unsigned long long llu;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define REP(i, a, b) for (ll i = a; i <= b; i++)
#define per(i, b, a) for (ll i = b; i >= a; i--)

const ll N = 3000005;

ll inv[N];

signed main() {
  ll n, p;
  scanf("%lld%lld", &n, &p);
  REP(i, 1, n)
  printf("%lld\n", inv[i] = i - 1 ? (-p / i * inv[p % i] % p + p) % p : 1);
}

// https://www.luogu.com.cn/record/60969822