转 https://blog.csdn.net/Cyan_rose/article/details/83065026
long long quick_mul(
long long x,
long long y,
long long mod) {
long long ans=
0;
while(y!=
0){
if(y&
1)ans+=x,ans%=
mod;
x=x+x,x%=
mod;
y>>=
1;
}
return ans;
}
long long quick_pow(
long long x,
long long y,
long long mod){
long long ans=
1;
while(y!=
0){
if(y&
1) ans=quick_mul(ans,x,mod)%
mod;
x=quick_mul(x,x,mod),x%=
mod;
y=y>>
1;
}
return ans;
}
龟速乘的根据&实现——慢工出细活
比起计算机自带的乘法，龟速乘的的运行速度还要慢上一些。
但是，它可以有效地保证你的long long不会boom的一声炸掉，然后送给你一个神奇的数字。
相信你一眼就能看出来，这两个东西长的不是一般的像。
如果再仔细观察一下就会发现，快速幂里的x是指数级增长，而龟速乘变成了翻倍，仅此而已。
龟速乘总结——快速幂的补充
实际上，龟速乘的确慢，甚至比直接用开始提到的循环乘法还要慢（因为龟速乘相当于一个自行取模的乘号），然而慢工出细活，正是它的慢最终为我们解决了数据过大时产生的问题。
归根结底，龟速乘的出发点就是为了解决弥补快速幂的BUG，因而其思想与快速幂也十分接近。用一点点时间换来数据范围的扩大，想来是个不亏的交易。
当然，平时不担心爆long long的情况下，就没必要把龟速乘加上了~
转载于:https://www.cnblogs.com/wifimonster/p/10206866.html
