算法
(逆元) $O(n)$
线性预处理出逆元即可。
具体推导见 推导
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
const int N = 3e6 + 10;
int n, p;
int inv[N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cin >> n >> p;
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (ll)(p - p / i) * inv[p % i] % p;
}
for (int i = 1; i <= n; ++i) cout << inv[i] << '\n';
return 0;
}