快速幂

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

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

$$a^b=\left\{\begin{aligned} &a^{\left\lfloor b/2\right\rfloor}\cdot a^{\left\lfloor b/2\right\rfloor} && b=2k\\ &a^{\left\lfloor b/2\right\rfloor}\cdot a^{\left\lfloor b/2\right\rfloor}\cdot a && b=2k+1 \end{aligned}\right. ,k\in\mathbb{Z}$$

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≤\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{aligned} a^b&=a^{\Large(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{aligned}$$

扫描 $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;
}