快速幂

定义

快速幂,二进制取幂(Binary Exponentiation,也称平方法),是一个在 $O(log\: n)$ 的时间内计算 $a^{n}$ 的小技巧，而暴力的计算需要 $O(n)$ 的时间。

这个技巧也常常用在非计算的场景，因为它可以应用在任何具有结合律的运算中。

––––摘于OIwiki

分析

我们算n个a相乘是,有时候会因为数据太大而超时,枚举的方法就不适用了.但是我们知道 $a^{b+c}=a^{b}\times a^{c}$ , $a^{nm}=(a^{n})^{m}$ .二进制取幂的想法是，我们将取幂的任务按照指数的 二进制表示 来分割成更小的任务。

于是我们只需要知道一个快速的方法来计算上述 3 的 $a^{k}$ 次幂的序列。这个问题很简单，因为序列中（除第一个）任意一个元素就是其前一个元素的平方。

举个栗子:

这么说,如果你想要计算 $3^{15}$ ,就可以推出以下式子:

$3^{15}=3^{1}\times 3^{2}\times 3^{4}\times 3^{8}=\cdots$

根据上述举例不难发现,求大数字的幂运算已经被我们转化成了形式相同的子运算

代码

代码的话我认为有两种思路,一种是递归实现,一种是非递归实现.

递归实现

long long qkpow(long long x,long long y){
    if(y==0){
        return 1;
    }
    long long res=qkpow(x,y/2);
    if(y%2){
        return res*res*x;
    }else{
        return res*res;
    }
}

非递归实现(通用方法)

由于递归的时间太慢了,所以我们一般不用递归来求快速幂,而是用普通的位运算来求快速幂,理论上两者的时间复杂度是相同的,都是 $O(log\: n)$ ,但是实践上第二种要比递归快得多

long long qkpow(long long x,long long y){
  long long res=1;
  while(y>0){
    if(y&1){
        res=res*x;
    }
    x=x*x;
    y>>=1;
  }
  return res;
}

模意义下取幂

模意义下取幂也是一种常见的算法思路,它也可以应用在许多方面,例如它可以用于计算模意义下的乘法逆元。

既然我们知道取模的运算不会干涉乘法运算，因此我们只需要在计算的过程中取模即可。

long long qkpow(long long x,long long y){
  long long res=1;
  while(y>0){
    if(y&1){
        res=res*x%m;
    }
    x=x*x%m;
    y>>=1;
  }
  return res;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/26579.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！