跳转至

快速幂

模板
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]}\) 的贡献。

// 需要一个普通快速幂
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;
}