跳转至

光速幂

在固定 \(a\) 和 \(P\) 的情况下，已知 \(b\)， \(O(1)\) 求 \(a^b\mod P\)

模版
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
struct LightSpeedPow {
    int mod, a, B, phi;
    vector<array<int, 2>> lsp;
    LightSpeedPow() = default;
    LightSpeedPow(int a, int mod) : a(a), mod(mod) {
        B = pow(mod, 0.5);
        lsp.resize(B + 1);
        lsp[0] = {1, 1};
        for (int i = 1 ; i <= B ; i++) {
            lsp[i][0] = 1LL * lsp[i - 1][0] * a % mod;
        }
        for (int i = 1 ; i <= B ; i++) {
            lsp[i][1] = 1LL * lsp[i - 1][1] * lsp[B][0] % mod;
        }
        phi = mod;
        int x = mod;
        for(int i = 2 ; 1LL * i * i <= x ; i++) {
            if (x % i == 0) {
                phi = phi / i * (i - 1);
                while (x % i == 0) x /= i;
            }
        }
        if (x != 1) phi = phi / x * (x - 1);
    }
    int operator()(int b) {
        if (b > phi) b %= phi;
        return 1LL * lsp[b % B][0] * lsp[b / B][1] %mod;
    }
}; // LightSpeedPow