这是一种不一样的线性逆元递推求法

其实也可以线性求出来任意一坨相乘得到的数的逆元

思路

根据逆元的意义,我们容易知道,如果我们知道$(xy)^{-1}(mod p)$,那么我们乘以$y$,就可以$O(1)$得到$x^{-1} (modp)$。

这样,$x$的逆元,可以利用$(x!)^{-1} \times (x - 1)!$这个式子求出来。所以,我们可以先递推出$n!$,然后用扩欧或者快速幂求出$(n!)^{-1}(modp)$,就可以反过来递推出$1$到$n$的所有逆元

代码

cout会超时,因为取消流同步和绑定只能加速cin

// luogu-judger-enable-o2
#include <iostream>

using namespace std;

const int MAXN = 3e6 + 5;

int fac[MAXN], inv[MAXN], n, p;

int Exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int ret = Exgcd(b, a % b, y, x);
    y -= 1LL * a / b * x;
    return ret;
}

void GetInv(int x, int finv, int mod) {
    if (x == 0) return;
    int ninv = 1LL * finv * fac[x - 1] % mod;
    GetInv(x - 1, 1LL * finv * x % mod, mod);
    //cout << ninv << endl;
    printf("%d\n", ninv);
}

int main() {
    //ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> p;
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = 1LL * fac[i - 1] * i % p;
    int x, y;
    Exgcd(fac[n], p, x, y);
    GetInv(n, (x + p) % p, p);
    return 0;
}