AcWing 89. a^b
原题链接
简单
作者:
Terrxzy
,
2021-02-09 14:08:36
,
所有人可见
,
阅读 2
自己打着看的题解
简单的快速幂模板题,那么这里就介绍一下快速幂是个什么东西
快速幂,顾名思义,是一种高效的求a^b mod p的方法,解决如本题一类的大数据问题
它的主要思路就是将b拆分,而这里拆分成2的次方数最方便
比如b=13 b拆为1+4+8
那么我们显然知道a^(x1+x2)=a^x1+a^x2
那么我们的a^13显然为a*a^4*a^8
而我们可以通过a^4方便的计算出a^8
这样我们就可以快速的求出a^b次方了
代码附上
#include<iostream>
using namespace std;
long long a,b,p,ans=1;
//a,b,p如题,ans为中间计算如a^2 a^4 a^8之类的东西的中间量,因为要不断的
int main(){
cin>>a>>b>>p;
while(b>0)
{
if (b&1) ans=ans*a%p;//如果i对应的二进制的位置上刚好为1,就可以计算了
b>>=1;//相当于b=b/2
//我们将b转化为2进制由此可以方便我们得出b由那几个2的次方数相加得到
//比如 b=13 二进制 1101 那么b=2^0+2^2+2^3=1+4+8
//假设我们有个东西i一开始指着二进制中的最右位
//那么这一步相当都将i左移一位
a=a*a%p;//a为中间计算如a^2 a^4 a^8之类的东西的中间量,要不断自乘,为了防止数据过大,要及时 mod
}
cout<<ans%p;
//有一个坑点,当p=1时,且b=0 我们的ans=1要是不 mod p的话输出为 1
//实际上输出为0 所以我们在最后还要 mod p
return 0;
}