快速幂算法介绍及简单实现

大家好，我是讯享网，很高兴认识大家。

讯享网

一、快速幂算法简介

快速幂算法（Exponentiation by Squaring）是一种用于计算幂运算的高效算法。它通过将指数进行二进制拆分，并利用指数的二进制表示形式来减少乘法和幂运算的次数，从而提高计算速度。

具体步骤如下：

1. 将指数以二进制形式表示

2. 从右向左遍历二进制数，如果当前位为1，则将底数乘以自身的平方，否则只将底数平方

3. 每次计算完毕后，将指数右移一位（相当于除以2）

4. 重复步骤2和步骤3，直到指数变为0

二、快速幂算法原理介绍

我们可以利用指数的二进制表示形式来减少乘法和幂运算的次数。对于任意一个指数n，可以将其表示为二进制形式的字符串，例如n=10110（对应十进制的22）。然后，我们可以根据二进制的每一位来决定是否进行乘法和平方操作。具体地，我们从最低位开始遍历二进制数，如果当前位为1，那么我们将底数a进行平方操作，并与之前得到的结果相乘；如果当前位为0，那么我们只进行平方操作。每次操作完毕后，将指数右移一位（相当于除以2），继续下一位的处理。最后得到的结果就是a^n的值。通过这种方法，我们将指数的二进制拆分为多个部分，每个部分只需要一次乘法和平方操作。由于指数的二进制位数是log n级别的，所以快速幂算法的时间复杂度为O(log n)，比普通的幂运算算法的时间复杂度O(n)更高效。

比如，如果 n 能被 2 整除，那我们可以先计算一半，得到 $a^{n / 2}$ 的值，再把这个值平方得出结果。这样做虽然有优化，但优化的程度很小，仍是线性的复杂度。
再比如，如果我们能找到 $2^{k}=n$ ，那我们就能把原来的运算优化成 $\left(\left(a^{2}\right)^{2}\right)^{2} \ldots$ ，只需要 k 次运算就可以完成，效率大大提升。可惜的是，这种条件显然太苛刻了，适用范围很小。不过这给了我们一种思路，虽然我们很难找到 $2^{k}=n$ ，但我们能够找到 $2^{k 1}+2^{k 2}+2^{k 3}+\ldots \ldots+2^{k m}=n$ 。这样，我们可以通过递推，在很短的时间内求出各个项的值。

我们都学习过进制与进制的转换，知道一个t进制数的值可以表示为各个数位的值与权值之积的总和。例如，2进制数1001，它的值可以表示为十进制的 $1 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0$ ，即9。这完美地符合了上面的要求。可以通过2进制来将n转化成 2^k_m 的序列之和，而2进制中第i位（从右边开始计数，值为1或是0）则标记了对应的 2^(i-1) 是否存在于序列之中。

通过这种方法，我们只需要计算 a、 a^2 、 a^4 、......直到a的 2^(km) 次方的值（这个序列中的项不一定都存在，取决于n的二进制表示），然后将它们相乘即可完成整个幂运算。使用位运算的操作可以很容易地实现这个算法，其复杂度为O(log n)。

三、快速幂算法简单实现

const int p=; long long fastmi(long long a,long long b){ long long ans=1,bose=a; while(b>0){ if(b&1==1) ans=ans*bose; bose=bose*bose; b>>=1; } return ans;

讯享网

四、常见问题和解决方案

如果题目中出现快速幂加上取余操作，那么题目中的数据量可能会非常庞大，在这种情况下减少时间和空间的操作就显得非常重要了。

解决方法是

1、所有的数据均使用long long操作

2、每一步进行多乘操作时均进行取余操作。（减小空间，防止long long承受不下）

3、二进制操作（二进制操作可以有效减少时间）

完整代码如下：

讯享网#include<iostream> using namespace std; long long p; long long fastmi(long long a,long long b){ long long ans=1,bose=a; while(b>0){ if(b&1==1) ans=ans*bose%p; bose=bose*bose%p; b>>=1; } return ans; } int main(){ long long m,n,endd; cin>>m>>n>>p; endd=fastmi(m,n); if(m==1&&n==0&&p==1) //这一步是周全特殊情况的讨论 endd=0; cout<<m<<"^"<<n<<" mod "<<p<<"="<<endd<<endl; return 0; }