题解：P1226 【模板】快速幂
IGA_Indigo
·
·
题解
题目大意
在 2\le a,b \le2^{31}、2\le p \le2^{31} 的限制下计算 a^b\mod p 的结果。
大体思路
由于 a 和 b 都很大，O(b) 的暴力相乘肯定会超时，我们需要想出 O(\log b) 的做法来处理幂运算。
我们首先要知道一个小学知识：
$(a^b)^c=a^{(b\times c)}$。
类似于倍增的二进制拆位思路，我们把 $a^b$ 可以拆成由若干个 $a^{(2^n)}$ 相乘组成的式子，这样我们就能把复杂度降到 $O(\log b)$。
拆的办法也很显然，把 $b$ 拆成由若干个由 $2^n$ 组成的式子，然后再将这几个 $a^{2^x}$ 乘起来。
就如样例的例子，$2^{10}$：
$10=2^3+2^1$。
所以：
$2^{10}=2^{2^3}\times 2^{2^1}$。
## 部分代码讲解
```cpp
int ans=1;
while(b) {
if(b%2==1) {
ans=ans*a%p;
}
b/=2;
a=a*a%p;
}
```
我们对 $b$ 进行处理，如果其不可以被二整除，那么我们就先把 $a^b$ 拆成 $a^{b-1}\times a$，用变量 $ans$ 记录这些被分出来的 $a$，可以被二整除或处理完后，我们将 $b$ 除以二，将 $a^b$ 拆为 $a^{b/2}\times a^{b/2}$，我们这里让当前的 $a$ 变为 $a^2$ 即可，之后的处理保留这次的平方。
## Code
```cpp
#include<bits/stdc++.h>
using namespace std;
int main() {
long long a,b,p;
cin>>a>>b>>p;
cout<<a<<"^"<<b<<" mod "<<p<<"=";
int ans=1;
while(b) {
if(b%2==1) {
ans=ans*a%p;
}
b/=2;
a=a*a%p;
}
cout<<ans;
return 0;
}
```
最后给大家一个考试时用的模板，作为自定义函数使用：
```cpp
long long ksm(long long a,long long b){
long long ans=1;
while(b){
if(b&1){
ans=ans*a%mod;
}
b>>=1;
a=a*a%mod;
}
return ans;
}
```