跳转至

快速幂

模板 
1
2
3
4
5
6
7
8
9
ll qpow(ll a, ll b) {
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

原理

\[ \begin{align*} &a^b\\ =&\prod_{i=0}^{\log b}{(a^{2^i})^{[b \text{ and } 2^i]}}\\ =&\prod_{i=0}^{\log b}{[b \text{ and } 2^i]?(a^{2^i}):1} \end{align*} \]

我们可以在循环的时候通过每次平方并取模的方式持续维护 \(a^{2^{i}}\)，这样既可以避免 \(2^{i}\) 太大，也能在很大程度上优化时间复杂度。

高精十进制快速幂

有时，快速幂的指数是一个十进制的高精度字符串。我们希望求出幂对 \(mod\) 取模的结果，可以考虑使用十进制快速幂解决。

\[ a^b=\prod_{i=0}^{\lg b}{(a^{b[i]\times 10^i})}=\prod_{i=0}^{\lg b}{({a^{10^i}})^{b[i]}} \]

由于 \(b\) 在十进制下的任意一位数字都很小，求出 \(a^{b[i]}\) 的时间复杂度可看作一个常数；我们可以像普通快速幂一样持续维护 \(a^{10^i}\) 取模的结果，并在第 \(i\) 位时对 res 产生 \(({a^{10^i}})^{b[i]}\) 的贡献。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// 需要一个普通快速幂
ll qpow(ll a, ll b) {
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

// 十进制快速幂
ll qpow(ll a, string b) {
    ll res = 1;
    for(int i = b.size() - 1; i >= 0; i--) {
        res = res * qpow(a, b[i] - '0');
        a = qpow(a, 10);
    }
    return res;
}