Irelia

Irelia

逝去的是刀锋,不变的是意志

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

posted on 2019-07-24 13:07:34 | under 题解 |

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

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

思路

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