快速幂

最后更新于2年前

快速幂

快速幂用于快速计算指数（ $2^n$ ），主要思想是二分。

由于计算机计算单个乘法比多个乘法快得多，所以利用二分的思想来减少乘法运算次数可以提高速度。

例： $7^{10} = 7*7*7*...*7$ 需要计算9次乘法，而先计算 $7^5$ 再计算 $7^{10}$ ，就只用计算 $7^5 = 7*7*7*7*7$ 和 $7^{10}=7^5*7^5$ ，只用5次乘法。

以此类推，得到一个递归二分的策略：

n是奇数：a^n = a^{n-1}*a^n\\ n是偶数：a^n = a^{n/2}*a^{n/2}\\ n=0：a^n = 1

写成代码：

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;
    else
    {
        ll temp = qpow(a, n / 2);
        return temp * temp;
    }
}

这是递归版本的快速幂。可以看到，这里二分的操作可以和二进制的右移对应，于是可以用二进制的方式理解：

由于上面的递归形式递归会耗费时间，所以用二进制的思路将上面的递归改成循环形式会更好。

代码：

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

上一页动态规划-java语言练习一：暴力DP 下一页状态压缩DP-java描述