题解 | #【模板】乘法逆元#

【乘法逆元】

方法1：线性求逆元，详细方式推导可以参考oi-wiki https://oi-wiki.org/math/number-theory/inverse/#_5

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3e6 + 10;

int n, p, inv[N];
signed main() {
    cin >> n >> p;
    inv[1] = 1;
    for (int i = 2; i <= n; i++) 
    	inv[i] = (p - (p / i) * inv[p % i] % p) % p;

    for (int i = 1; i <= n; i++) 
    	cout << inv[i] << "\n";

    return 0;
}

方法2：因为$nn$​的数据范围比较大，所以不能用费马小定理+快速幂硬求，考虑如何减少用快速幂求逆元的次数。

对于数组$a_1,a_2,a_3,a_{4}a\_1,a\_2,a\_3,a\_4$​，若要求$a_{2}a\_2$​的逆元，只需要求$a_2^{-1}=(a_1{a}_2{a}_3{a}_4{)}^{-1}\cdot (a_1{a}_3{a}_4)a\_2^\{-1\}=(a\_1a\_2a\_3a\_4)^\{-1\}\backslash cdot\; (a\_1a\_3a\_4)$​，记录一个前缀和一个后缀就行了。（当时写的时候并不会线性求逆元）

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3e6 + 10;
int n, p, pre[N], suf[N];
int k = 1;

int power(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = (__int128)res * a % p;
        a = (__int128)a * a % p;
        b >>= 1;
    }
    return res;
}

int inv(int x) { return power(x, p - 2); }

signed main() {
    cin >> n >> p;
    for (int i = 1; i <= n; i++) k = (__int128)k * i % p;
    k = inv(k);

    pre[0] = suf[n + 1] = 1;
    for (int i = 1; i <= n; i++) pre[i] = (__int128)pre[i - 1] * i % p;
    for (int i = n; i >= 1; i--) suf[i] = (__int128)suf[i + 1] * i % p;

    for (int i = 1; i <= n; i++) {
        int inv_i = (__int128)pre[i - 1] * suf[i + 1] % p * k % p;
        cout << inv_i << "\n;
    }
    return 0;
}