逆元

拓展欧几里得法

1
2
3
4
5
6
7
8


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

快速幂法

1
2
3
4
5
6
7
8
9


int qpow(long long a, int b) {
    int ans = 1;
    a = (a % p + p) % p;
    for (; b; b >>= 1) {
        if (b & 1) ans = (a * ans) % p;
        a = (a * a) % p;
    }
    return ans;
}

线性求逆元

1
2
3
4


    inv[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv[i] = (long long)(p - p / i) * inv[p % i] % p;
    }

线性求任意n个数逆元

1
2
3
4
5
6


    s[0] = 1; //s 为前缀积
    for (int i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % p; // a 为 n 个任意数
    sv[n] = qpow(s[n], p - 2);
    // 当然这里也可以用 exgcd 来求逆元,视个人喜好而定.
    for (int i = n; i >= 1; --i) sv[i - 1] = sv[i] * a[i] % p;
    for (int i = 1; i <= n; ++i) inv[i] = sv[i] * s[i - 1] % p;