龜速乘，快速乘法

龜速乘

在遇到求兩個>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);

比龜速乘短，不過容易丟失精度

出自集訓隊論文