提升幂运算速度的算法：快速幂

快速幂

复杂度

时间复杂度：$O(\log_2n)$

（$n$ 为幂数）

代码实现

long long fastpow(long long a, long long b)
{
    long long ans = 1;
    while (b)
    {
        if (b % 2 == 1)
            ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}

算法思路

$2^{32}=4^{16}=16^{8}=256^{4}=65536^{2}=4294967296$

如果用一般的循环算法，$2^{32}$ 需要循环 32 次，而通过上面的方法，我们只用了 $\log_{2}32=5$ 次循环，就得出了答案，这指数较小时差别不大，但指数非常大时差别会很大。

当然实际情况不会像上面那么顺利，指数不一定能够一直为偶数，所以需要一些额外操作。

以 $3^{11}$ 为例：

指数为奇数 $11$，单独分出一个底数 $3$，即 $3^{11}=3\times 3^{10}$，把分出的底数 $3$ 乘入 $ans$，现在 $ans = 3$

指数为偶数 $10$，可以将指数除二，即 $3^{10}=9^{5}$，现在底数为 $9$，指数为 $5$

指数为奇数 $5$，单独分出一个底数 $9$，即 $9^{5}=9\times9^{4}$，把分出的底数 $9$ 乘入 $ans$，现在 $ans = 27$

指数为偶数 $4$，可以将指数除二，即 $9^{4}=81^{2}$，现在底数为 $81$，指数为 $2$

指数为偶数 $2$，可以将指数除二，即 $81^{2}=6561^{1}$，现在底数为 $6561$，指数为 $1$

指数为奇数 $1$，单独分出一个底数 $6561$（实际上就是全部），把分出的底数 $6561$ 乘入 $ans$，现在 $ans = 177147$

指数为 $0$，循环结束，得到 $3^{11}=177147$

在代码中，实际上分出一个底数后，并没有特意将指数减一，而是直接继续操作，原因是之后除二后，整型被截断，一样能得到正确结果，例如上面的 11 >> 1 = 5, 5 >> 1 = 2（整型右移其实和除二一样）

大数取模

一般能用到快速幂算法的，答案都会非常巨大，肯定是超出已有数据类型范围的，所以题目一般会说答案对某个数字取模。快速幂可以完成这个操作，只需要进行很小的修改。

const long long MOD = 20220128;
long long fastpow(long long a, long long b)
{
    a %= MOD; // 开头先取一次模
    long long ans = 1;
    while (b)
    {
        if (b % 2 == 1)
            ans = ans * a % MOD; // 每次运算都取模
        a = a * a % MOD; // 每次运算都取模
        b >>= 1;
    }
    return ans;
}