快速幂应用

快速幂，也称平方求幂，可以在O(nlogn)时间复杂度内计算乘方，在许多算法中如大数求余中被广泛应用。

问题引出

如计算7的10次方，怎么算比较快？

普遍的想法是10个7一直乘下去，共执行9次乘法运算。这样是比较慢的，而且也没发挥出cpu的高性能计算。

于是，我们可以进行一个拆分操作。先7×7=49，然后7的5次方49×49×7=16807，再然后7的5次方乘7的5次方，计算得到7的10次方。

算法思路

以上可概述为一个二分的思想，并且得到一个递归方程：

代码实现

原理代码

1
2
3
4
5
6
7
8
9
10
11
12
13
//递归快速幂
int quick_pow(int a, int n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return quick_pow(a, n - 1) * a;
    else
    {
        int temp = quick_pow(a, n / 2);
        return temp * temp;
    }
}

注意，这个temp变量是必要的，因为如果不把[公式]记录下来，直接写成quick_pow(a, n /2)*quick_pow(a, n /2)，那会计算两次[公式]，整个算法就退化为了 [公式] 。

快速幂模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//模板1
public double myPow(double x, int n) {
        double ans = 1, temp = x;
        int exp = n;
        while (exp != 0) {
            if ((exp % 2) != 0) {
                ans = ans * temp;
            }
            temp = temp * temp;
            exp /= 2;
        }
        return n > 0 ? ans : 1 / ans;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//模板2
class Solution {
public:
    //题解：快速幂
    double myPow(double x, int n) {
        double res=1.0;
        int i=n;
        while(i){
            if(i&1)res*=x;  //i的低位存在，res*x
            x*=x;           //x扩大为它的平方，因为二进制每位的差距是平方关系
            i/=2;           //i向0靠近
        }
        return n<0?1/res:res;
    }
};

实际应用

在实际问题中，题目常常会要求对一个大素数取模(%1000000007)，这是因为计算结果可能会非常巨大，但是在这里考察高精度又没有必要。这时我们的快速幂也应当进行取模，此时应当注意，原则是步步取模，如果MOD较大，还应当开long long。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//递归快速幂（对大素数取模）
#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;
    }
}

例题

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m] 。请问 k[0]k[1]…*k[m] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int b = n % 3, p = 1000000007;
        long rem = 1, x = 3;
        for(int a = n / 3 - 1; a > 0; a /= 2) {
            //快速幂取模
            if(a % 2 == 1) rem = (rem * x) % p;
            x = (x * x) % p;
        }
        if(b == 0) return (int)(rem * 3 % p);
        if(b == 1) return (int)(rem * 4 % p);
        return (int)(rem * 6 % p);
    }
}