快速幂

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取余结果都一样,就能保证你的代码是正确的。

2.推导

003

3.相关链接

P1226 【模板】快速幂||取余运算

8分钟学会快速幂算法...

大整数取余

Last modification:February 4th, 2020 at 05:52 am
如果觉得我的文章对你有用,请随意赞赏