快速乘 学习

转自:https://www.cnblogs.com/812-xiao-wen/p/10543023.html

1.通过位运算

inline ll ksc(ll x,ll y,ll p){//计算x乘y的积
    ll res=0;//加法初始化
    while(y){
        if(y&1)res=(res+x)%p;//模仿二进制
        x=(x<<1)%p; y>>=1;//将x不断乘2达到二进制
    }return res;
}
// ll 表示 long long

这里说明(A*B)%C=(A%C)*(B%C),(A+B)%C=A%C+B%C,也就是先乘再模=先模再乘,先加再模=先模再加。

这个方法经常被用于两数相乘取模的场景,如果两数相乘已经超过数据范围,但取模后不会超过,我们就可以利用这个方法来拆位取模计算贡献,保证每次运算都在数据范围内。

 

上一篇:有理数加法


下一篇:输入两个正整数m和n,求其最大公约数和最小公倍数。