快速幂

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

递归写法

根据乘方公式 $a^{m+n}=\phantom{0}$$\phantom{0}{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=\phantom{0}$$\phantom{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,\phantom{0}$$\phantom{0}{k}_2,\phantom{0}$$\phantom{0}{k}_3,\phantom{0}$$\phantom{0}\cdots$ 位为 $1$，则 $b=\phantom{0}$$\phantom{0}{2}^{k_1}+\phantom{0}$$\phantom{0}{2}^{k_2}+\phantom{0}$$\phantom{0}{2}^{k_3}+\phantom{0}$$\phantom{0}\cdots (k_i\le \log b)$。

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

将 $b=\phantom{0}$$\phantom{0}{2}^{k_1}+\phantom{0}$$\phantom{0}{2}^{k_2}+\phantom{0}$$\phantom{0}{2}^{k_3}+\phantom{0}$$\phantom{0}\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;
}