信息竞赛笔记(2)––快速幂-Toy模板网

这篇具有很好参考价值的文章主要介绍了信息竞赛笔记(2)––快速幂。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

快速幂

定义

分析

代码

递归实现

非递归实现(通用方法)

模意义下取幂

快速幂

定义

快速幂,二进制取幂(Binary Exponentiation,也称平方法),是一个在的时间内计算的小技巧，而暴力的计算需要的时间。

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

––––摘于OIwiki

分析

我们算n个a相乘是,有时候会因为数据太大而超时,枚举的方法就不适用了.但是我们知道 $信息竞赛笔记(2)––快速幂$ ,.二进制取幂的想法是，我们将取幂的任务按照指数的 二进制表示 来分割成更小的任务。

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

举个栗子:

信息竞赛笔记(2)––快速幂

这么说,如果你想要计算,就可以推出以下式子:

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

代码

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

递归实现

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

非递归实现(通用方法)

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

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

模意义下取幂

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

既然我们知道取模的运算不会干涉乘法运算，因此我们只需要在计算的过程中取模即可。文章来源地址https://www.toymoban.com/news/detail-471039.html

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

到了这里，关于信息竞赛笔记(2)––快速幂的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！