算法详解1——快速幂

· · 个人记录

前言

快速幂是一个可以快速算出 a^b 的算法，复杂度可达 O(logn) 级别，它广应用于需要快速算出两个正整数的幂的地方。快速幂基于的是倍增算法，将 b 拆成二进制计算，利用快速幂还可以计算矩阵速幂等。

目录

  1. 快速幂的概念及过程

  2. 代码实现

    第一部分：快速幂的概念及过程

    正常情况下，如果我们要计算 a^b，那么我们会直接循环 b 次，每次乘上 a，代码如下：

    int res=1;
for (int i=1;i<=b;i++) res*=a;

但这种算法的时间复杂度是 O(n) 的，在一些程序中若是用它很容易TLE。于是人们发明了快速幂，这种算法的时间复杂度可达到 O(logn)，远远低于朴素算法。那这种算法该怎么做呢？

在讲速幂之前，我们先得明确一个概念：

a^{b+c}=a^b\cdot a^c

证明很简单,因为 b+c 个 a 乘在一起，就相当于 b 个 a 乘在一起乘上 c 个 a 乘在一起。

明确完这个，咱们再想想，根据二进制原理，每个整数都可以拆分成 2 的幂次的形式。比如：

8=2^3

10=2^3+2^1

15=2^3+2^2+2^1+2^0

那么，如果我们把 a^b 中的 b 二进制形式，比如 2^{15}，可以拆成以下形式：

2^{15}=2^{2^3+2^2+2^1+2^0}

在根据刚刚讲的第一个概念，可以转换成：

2^{2^3+2^2+2^1+2^0}=2^{2^3}\cdot 2^{2^2}\cdot 2^{2^1}\cdot2^{2^0}

我们又知道：

2^{2^1}=(2^{2^0})^2

2^{2^2}=(2^{2^1})^2

2^{2^3}=(2^{2^2})^2

即：

a^{2^b}=(a^{2^{b-1}})^2

所以我们可以设定一个变量 tmp，开始 tmp=2,每次 tmp=tmp^2。由于 (15)_ {10}=(1111)_ 2，所以从低位开始，每次遇到 1 就乘上 tmp，由于 4 位都是 1，所以每次都要乘上 tmp，最后答案为：

2\cdot 2^2\cdot 2^{2^2}\cdot 2^{2^{2^2}} = 2\cdot 4\cdot 16\cdot 256 = 32768

所以

2^{15}=32768

由此，我们总结出了快速幂的基本步骤：对于 a^b，先将 b 拆成二进制形式，再设 tmp=a，从低位开始，每遇到一个 1，就乘上 tmp，每次还要 tmp=tmp^2，最后我们就能算出 a^b 的答案。

这样做的时间复杂度是多少呢？因为我们只需要一个拆解成二进制的循环，复杂度为 O(log_2n)，所以总时间复杂度就是 O(log_2n)，即 O(logn)。

第二部分：代码实现

代码如下：

int pw(ll a,ll b,ll p)//p是模数，因为有时候答案可能爆long long，所以要取摸p
{
    int res=1,tmp=a;//初始值
    while (b>0)//二进制分解
    {
        if (b%2)//如果是1
        {
            res*=tmp;
            res%=p;//防止爆long long，取模p
        }
        tmp=tmp*tmp;//tmp自乘
        tmp%=p;
        b/=2;
    }
    return res;
}

推荐题目：

P1226 【模板】快速幂

结语

快速幂的知识点就讲到这了。这是本蒟蒻第一次发算法解析，若其中有错误之处，欢迎大家指出！

本人洛谷号（欢迎关注）