题解 P3811 【【模板】乘法逆元】

· · 题解

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

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

思路

根据逆元的意义，我们容易知道，如果我们知道(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;
}