转自: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,也就是先乘再模=先模再乘,先加再模=先模再加。
这个方法经常被用于两数相乘取模的场景,如果两数相乘已经超过数据范围,但取模后不会超过,我们就可以利用这个方法来拆位取模计算贡献,保证每次运算都在数据范围内。