龟速乘，快速乘法

龟速乘，快速乘法

---

龟速乘

在遇到求两个>1e9的数相乘mod m且m>1e9的情况下long long 会爆

我们便可以采取龟速乘来避免

ll mul(ll x,ll y,ll mod){
	ll ans=0;
	while(y){
		if(y&1) ans+=x,ans%=mod;
		x+=x;
		x%=mod;
		y>>=1;
	}
}

原理便是把所乘数二进制分解

比如207=20(4+2+1)

该算法效率低于乘法

所以叫做龟速乘

快速乘

cin>>a>>b>>mod;
    	cout<<((a*b-(ll)((long double)a*b/mod)*mod+mod)%mod);

比龟速乘短，不过容易丢失精度

出自集训队论文