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

快速幂

时间复杂度:$O(\log_2N)$

代码实现:

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(整型右移其实和除二一样)

大数取模:

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

#define 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;
}

标签: 快速幂

添加新评论