C++ 快速幂运算

1.概念：快速幂运算也叫反复平方法。顾名思义，算法就蕴含在名字中。

2.原理：

假设要求x^n，如果n = 2^k，那么原题可以很轻松的表示为：x^n = ((x^2)^2)^2…。这样只要做k次平方运算就能解决，时间复杂度就从O(n)下降到log(n)。

由上面的分析可知，只要幂运算的幂可以写成2^k的形式，就可以用上面的方法降低时间复杂度。所以我们可以将任意的实数n改写有限个2^k的形式的相加。例如：

如图所示，x^22可以改写成x^16x^4x^2。这样我们就可以分别对x^16和x^4以及x^2使用上述方法快速计算结果，最后只要相加就可以了。

3.代码实例：

typedef long long ll;
ll quick_pow(ll x,ll n,ll m){
    ll res = 1;
    while(n > 0){
        if(n & 1)   res = res * x % m;
        x = x * x % m;
        n >>= 1;//相当于n=n/2.详情请参考位移运算符。
    }
    return res;
}

4.另一种理解方法

• 当b为偶数时，a^b可以转为a^2的b/2次方。
• 当b为奇数时，a^b可以转为a^2的b/2次方，再乘以a。
  像这样不断递归下去，每次n都减半，于是可以在n(logn)时间内完成幂运算。
  4.2代码实例：

ll q_pow(ll x,ll n,ll m){
    if(n == 0)  return 1;
    ll res = q_pow(x * x % m,n/2,m);
    if(n & 1)   res = res * x % m;
    return res;
}

代码很精简，需要仔细看。其中包含了模运算的相关知识，请自行百度。



原文链接: https://www.cnblogs.com/long98/p/10352245.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍