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