[算法/模板]快速幂

[算法/模板]快速幂

一、定义

快速幂是一种能在\(O(logN)\)的时间复杂度内计算出\(a^b\)的一种算法。
快速幂是常用的一种算法。

二、实现原理

实际上，\(a^b\)是b个a的连乘式，我们可以使用朴素算法在O(N)的时间内处理完毕。面对较小数据，我们还可以使用\(pow(a,b)\)来计算。一旦当数据范围过大或计算的数据超出我们已知的数据类型，这时候就需要使用快速幂进行处理。

就像倍增法，RMQ问题中的ST表，以及LCA的倍增求法，无疑都与"二"有关。快速幂也是这样的处理方法，即二进制拆分法。我们将一个底数\(a\)使用二进制分解成\(logN\)部分处理。下面我们用具体的例子来解释：

例如我们要计算\(3^{14}\)的值：
\((14)_{10}=(1110)_{2}=2^3+2^2+2^1\)。我们可以发现任意一个正整数都能拆分成诸如\(2^k\)连加的形式。且只有当二进制为1的时候才会被累加。因此我们只要不断地乘上底数3，在指数最低位为1的时候存储到res变量内，每次处理后右移一位。这就是快速幂的实现原理。

三、模板

以下为快速幂的模板(非递归):

int quick_pow(int a,int b){
    int res=1;//记得赋值为1！
    while(b){
        if(b&1) res=res*a;//最低位为1
        b>>=1;a=a*a;
    }
    return res;
}

四、例题

P1226 【模板】快速幂||取余运算
代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll b,p,k;
inline ll quick_pow(ll b,ll p,ll k){
    ll res=1;
    while(p){
        if(p&1) res=(res*b)%k;
        p>>=1;
        b=(b*b)%k;
    }
    return res%k;
}
int main()
{
    scanf("%lld%lld%lld",&b,&p,&k);
    printf("%lld^%lld mod %lld=%lld",b,p,k,quick_pow(b,p,k));
    return 0;
}