快速幂

说明：

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

让我们先来思考一个问题：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(logn)$$时间内计算出幂的算法，也就是快速幂。

Java模板(迭代法)

1
2
3
4
5
6
7
8
9
10
static long qpow(long a,int n){
    long sum =1;
    while(n!=0){
        if((n&1)!=0)
            sum=sum*a;
        a=a*a;
        n>>=1;
    }
    return sum;
}

C++模板(迭代法)

1
2
3
4
5
6
7
8
9
10
11
//非递归快速幂
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;
}

C++模板(递归法)

1
2
3
4
5
6
7
8
9
10
11
12
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;
    }
}