快速幂
1.模板
ll power(ll a,ll b,ll p)
{
int ans = 1%p;
for(;b;b>>=1){
if(b&1){
ans = ans *a %p;
}
a = a*a%p;
}
return ans;
}
关于取余操作:
1.对于100%的数据,0<=b、p、k<<2的32次方,也就是int 范围,两个int数相乘我们要用long long 才不会超出范围,第一个参数a是式子中递推每个单项的值,每次都要平方,所以要用long long。
2.我们再次理解下视频中第二个式子的含义,多个数的积对k取余,等于每项依次相乘的积对K取余。因为三个int数相乘有可能造成long long 溢出,所以,每两次a相乘的时候就要对K取余,因为K的范围是int ,所以其结果也是int。
3.实际上式子就是多个a相乘,而ans作为结果输出,这里也有可能会溢出,所以要作出同理的操作。
4.为什么要对k取余,我的理解是这样,不保证对,因为不对K取余,这个值就会变的很大,就要转换成大数操作,如果每个快速幂的题都要处理成大数,挺麻烦的,只要足够多的数据对K取余结果都一样,就能保证你的代码是正确的。