快速幂

文章转载自算法学习笔记(4)：快速幂 - 知乎 (zhihu.com)，如有侵权，请联系作者删除

---

快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以以\(O(log_2n)\)的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。

让我们先来思考一个问题：7的10次方，怎样算比较快？

方法1：最朴素的想法，7 * 7=49，49 * 7=343，... 一步一步算，共进行了9次乘法。

这样算无疑太慢了，尤其对计算机的CPU而言，每次运算只乘上一个个位数，无疑太屈才了。这时我们想到，也许可以拆分问题。

方法2：先算7的5次方，即7 * 7 * 7 * 7 * 7，再算它的平方，共进行了5次乘法。

但这并不是最优解，因为对于“7的5次方”，我们仍然可以拆分问题。

方法3：先算7 * 7得49，则7的5次方为49 * 49 * 7，再算它的平方，共进行了4次乘法。

模仿这样的过程，我们得到一个在\(O(log_2 n)\)时间内计算出幂的算法，也就是快速幂。

---

递归快速幂

刚刚我们用到的，无非是一个二分的思路。我们很自然地可以得到一个递归方程： \[ a^n=\left\{ \begin{aligned} a^n*a & &if\ n\ is\ odd\\ a^{\frac{n}{2}}*a^{\frac{n}{2}} & &if\ n\ is\ even\ but\ not\ 0 \\ 1 & &if\ n\ is\ 0 \end{aligned} \right. \]

对应的递归形式写法如下

//递归快速幂
int qpow(int a, int n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a;
    else
    {
        int temp = qpow(a, n / 2);
        return temp * temp;
    }
}

注意：这个temp不能省略，如果写成了qpow(a,n/2) * qpow(a,n/2)，那会计算两次\(a^\frac{n}{2}\)，时间复杂度会退化成\(O(n)\)

经常会遇到取模类的问题，这里我们的应对策略是在利用快速幂进行计算时也需要取模，此时应当注意：原则是步步取模，如果mod较大，还需开long long

//递归快速幂（对大素数取模）
#define MOD 1000000007
typedef long long ll;
ll qpow(ll a, ll n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a % MOD;
    else
    {
        ll temp = qpow(a, n / 2) % MOD;
        return temp * temp % MOD;
    }
}

递归快速幂的缺点是：产生额外的空间开销。我们可以把递归改写为循环，来避免对栈空间的大量占用，也就是非递归快速幂

---

非递归快速幂

//非递归快速幂
int qpow(int a, int n){
    int ans = 1;
    while(n){
        if(n&1)        //如果n的当前末位为1
            ans *= a;  //ans乘上当前的a
        a *= a;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;
}

以\(7^{10}\)为例，转换为计算\(7^{1010_{(2)}}\)，我们可以把它拆成\(7^{1000_{(2)}}\)和\(7^{10_{(2)}}\)，由此类推，任何数都可以拆分成若干个\(a^{(100···)_{(2)}}\)的形式相乘，恰好对应的就是\(a^1\)、\(a^2\)、\(a^4\) ······来计算，只需要不断地对底数平方即可算出它们

可以结合代码进行理解（如果实在看不懂只能看看原作者的文章了qwq）

---

快速幂的拓展

快速幂算法的应用范围实际上不止于此：在计算\(a^{\frac{n}{2}}\)时，只要a的数据类型支持乘法且满足结合律，快速幂的算法都是有效的。矩阵、高精度整数，都可以照搬这个思路。

//泛型的非递归快速幂
template <typename T>
T qpow(T a, ll n)
{
    T ans = 1; // 赋值为乘法单位元，可能要根据构造函数修改
    while (n)
    {
        if (n & 1)
            ans = ans * a; // 这里就最好别用自乘了，不然重载完*还要重载*=，有点麻烦。
        n >>= 1;
        a = a * a;
    }
    return ans;
}

注意

此时的时间复杂度不再是\(O(log_2\ n)\)，此时还与底数的乘法的时间复杂度有关。