快速幂

如何快速求 $a^b$（$a,b\in \mathbb{Z}$）？

递归写法

根据乘方公式 $a^{m+n}=a^m\cdot a^n$，有：

$$a^b=\{\begin{array}{rlrl}& a^{\lfloor b/2\rfloor }\cdot a^{\lfloor b/2\rfloor }& & b=2k\\ & a^{\lfloor b/2\rfloor }\cdot a^{\lfloor b/2\rfloor }\cdot a& & b=2k+1\end{array},k\in \mathbb{Z}$$

• 边界条件：$a^0=1$；
• 时间复杂度：$O(\log b)$。

typedef long long LL;

LL Pow(LL a, LL b) {
    if (!b) return 1; // 边界条件
    LL res = Pow(a, b / 2);
    if (b % 2 == 0)   // b 是偶数
        return res * res;
    else              // b 是奇数
        return res * res * a;
}

递推写法

若 $b$ 在二进制下的第 $k_1,k_2,k_3,\cdots$ 位为 $1$，则 $b=2^{k_1}+2^{k_2}+2^{k_3}+\cdots (k_i\le \log b)$。

举个例子，$(14{)}_{10}=(1011{)}_2$，二进制下 $14$ 的第 $0,1,3$ 位都为 $1$，那么 $14=2^0+2^1+2^3$。

将 $b=2^{k_1}+2^{k_2}+2^{k_3}+\cdots$ 代入 $a^b$：

$$\begin{array}{rl}{a}^b& =a^{(2^{k_1}+2^{k_2}+2^{k_3}+\cdots )}\\ & =a^{2^{k_1}}\cdot a^{2^{k_2}}\cdot a^{2^{k_3}}\cdot \cdots \end{array}$$

扫描 $b$ 的每个二进制位，如果第 $k$ 位是 $1$，则将答案乘上 $a^{2^k}$。

时间复杂度为 $O(\log b)$。

typedef long long LL;

LL Pow(LL a, LL b) {
    LL res = 1;
    while (b) {
        if (b % 2 == 1) // 二进制下该位为 1
            res *= a;
        a *= a, b /= 2;
    }
    return res;
}

更多时候，需要求对 $m$ 取模的快速幂结果，那么需要全程取模：

typedef long long LL;

LL Pow(LL a, LL b, LL m) {
    LL res = 1;
    while (b) {
        if (b & 1) // 等价于 b % 2 == 1
            res = (res * a) % m;
        a = (a * a) % m;
        b >>= 2;
    }
    return res;
}