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

news/2024/12/20 2:13:36/

快速幂

定义

分析

代码

递归实现

非递归实现(通用方法)

模意义下取幂

快速幂

定义

快速幂,二进制取幂(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;
}