跳转至

逆元

线性递推公式

\[ \nonumber inv(i)=(p-\dfrac{p}{i})*inv(p\ mod\ i)\ mod\ p \]

快速逆元

在 \(P\) 固定的情况下，已知\(a\)，求 \(\dfrac{1}{a}\mod P\)

模版

#110. 乘法逆元 - LibreOJ

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
struct Inverse {
    int B, B2, mod;
    vector<int> inv, pre, suf;
    vector<pair<int, int>> s;
    Inverse() = default;
    Inverse(int mod) : mod(mod) {
        B = pow(mod, 0.3333333333);
        B2 = B * B;
        inv.resize(mod / B + 1);
        inv[1] = 1;
        for (int i = 2, j = mod / B ; i <= j ; i++) {
            inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
        }
        s.resize(B2 + 1);
        pre.resize(B2 + 1);
        suf.resize(B2 + 1);
        s[0] = {0, 1};
        s[B2] = {1, 1};
        pre[B2] = suf[B2] = B2;
        for (int i = 2 ; i <= B ; i++) {
            for (int j = 1 ; j < i ; j++) {
                int pos = 1LL * j * B2 / i;
                if (pre[pos]) continue;
                pre[pos] = suf[pos] = pos;
                s[pos] = {j, i};
            }
        }
        for (int i = 1 ; i <= B2 ; i++) {
            if (pre[i] == 0) {
                pre[i] = pre[i - 1];
            }
        }
        for (int i = B2 ; i > 0 ; i--) {
            if (suf[i] == 0) {
                suf[i] = suf[i + 1];
            }
        }
    }
    int calc(int T, pair<int, int> x) {
        long long pos = 1LL * T * x.second;
        if (llabs(pos - 1LL * mod * x.first) > mod / B) return -1;
        pos %= mod;
        if (pos <= mod / B) return 1LL * x.second * inv[pos] % mod;
        return mod - 1LL * x.second * inv[mod - pos] % mod;
    }
    int operator()(int x) {
        x %= mod;
        if (x <= mod / B) return inv[x];
        int pos = 1LL * x * B2 / mod, res = calc(x, s[pre[pos]]);
        if (res == -1) res = calc(x, s[suf[pos]]);
        return res;
    }
}; // Inverse

在线 O(1) 逆元 - Problem - QOJ.ac

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
const int B = 1 << 10, T = 1 << 20;
struct Inverse {
    int mod;
    int f[T + 1], p[T + 1], buf[T * 3 + 3], *I = buf + T;
    Inverse(int mod) : mod(mod) {
        for (int i = 1 ; i <= B ; i++) {
            int s = 0, d = i << 10;
            for (int j = 1 ; j <= T ; j++) {
                if ((s += d) >= mod) s -= mod;
                if (s <= T) {
                    if (f[j] == 0) {
                        f[j] = i;
                        p[j] = s;
                    }
                } else if (s >= mod - T) {
                    if (f[j] == 0) {
                        f[j] = i;
                        p[j] = s - mod;
                    }
                } else {
                    int t = (mod - T - s - 1) / d;
                    s += t * d;
                    j += t;
                }
            }
        }
        I[1] = f[0] = 1;
        for (int i = 2 ; i <= T << 1 ; i++) {
            I[i] = 1LL * (mod - mod / i) * I[mod % i] % mod;
        }
        for (int i = -1 ; i >= -T ; i--) {
            I[i] = mod - I[-i];
        }
    }
    int operator()(int x) {
        return 1LL * I[p[x >> 10] + (x & 1023) * f[x >> 10]] * f[x >> 10] % mod;
    }
}; // Inverse