题解：P1226 【模板】快速幂
langmouren
·
·
题解
快速幂 算法介绍
为什么要使用快速幂
如果按照正常方式求幂，则时间复杂度为 O(b)，速度在某些题是不够的（例如本题就只能拿到 60 分）。
所以前人们想到了一种方法，能够在 O(\log_2 b) 的时间内计算出结果。
快速幂举例
注：本章节仅举例，为什么要这么操作请见下文“算法正确性证明”。
首先约定一个初始值为 1 的 ans 为答案。
例如，我们要计算 a^{11}，我们先把 11 拆成二进制的 1011。
$101$ 的最后一位是 $1$，把 $ans$ 赋值为 $ans \times a$，$a$ 赋值为 $a \times a$，随后右移 $101$，使其变为 $10$。
$10$ 的最后一位是 $0$，把 $a$ 赋值为 $a \times a$，随后右移 $10$，使其变为 $1$。
$1$ 的最后一位是 $1$，把 $ans$ 赋值为 $ans \times a$，$a$ 赋值为 $a \times a$，随后右移 $1$，使其变为 $0$。
$0$ 运行下去没有任何意义了，结束。
此时我们就得到了正确的结果。
## 正确性证明
### 算法正确性证明
快速幂使用**二进制**来加快计算。
例如，我们要计算 $a^{11}$，因为 $11$ 的二进制是 $1011$，我们可以转换出以下内容：
$$
\begin{aligned}
a^{11} &= a^{1011(2)} \\
&= a^{2^3 \times 1 + 2^2 \times 0 +2^1 \times 1 +2^0 \times 1}\\
&= a^{2^3 \times 1+2^1 \times 1 +2^0 \times 1}\\
&= a^{2^3} \times a^{2^1} \times a^{2^0}
\end{aligned}
$$
不需要有惊人的注意力就能发现，它的结果只和二进制中的**非零项**有关，所以在计算时我们只需要计算当前二进制位为 $1$ 的位。
我们还可以通过指数的运算性质知道：
$$a^{2^b} \times a^{2^b} = a^{2 \times 2^b} = a^{2^{b+1}}$$
高次幂可以通过低次幂求出，那么答案一定也可以从低次幂求出。
同时，由模运算的性质可以知道，在快速幂的运算过程中取模不会影响答案的正确性。
### 时间复杂度证明
对于任何一个数 $b$，它有 $\lfloor \log_2 b \rfloor + 1 $ 个二进制位，所以时间复杂度为 $O(\log_2 b)$。
## 代码实现
```cpp
#include<bits/stdc++.h>
using namespace std;
long long a,b,p,ans=1;
long long poww(long long a,long long b,long long p){
while(b>0){//如果b还不是0
if(b&1) ans=ans*a%p;//如果最低位是1 就把ans*a
a=a*a%p;//不论最低位是不是1，a都需要自乘以升幂
b>>=1;//b右移一位
}
return ans;
}
int main(){
scanf("%d%d%d",&a,&b,&p);
printf("%d^%d mod %d=%d",a,b,p,poww(a,b,p));
return 0;
}
```