[ long long multiply long long mod long long ] long long 乘 long long 模 long long不溢位算法

這標題有點長，不過也很清楚的顯示了這篇的重點，所以就直接附模板吧
如果a,b<m的話a%=m,b%=m;可以拿掉沒關係

code(比較慢，但適用範圍更大，算法取自維基百科:同餘):

	using ull = unsigned long long;
	ull _mod_mul(ull a,ull b,ull m){
	a%=m,b%=m;
	ull ans=0;
	for(;b;b>>=1){
	if(b&1){
	ans+=a;
	if(ans>=m)ans-=m;
	}
	a<<=1;
	if(a>=m)a-=m;
	}
	if(ans>=m)ans-=m;
	else if(ans<0)ans+=m;
	return ans;
	}

view raw mod_mul1.cpp hosted with ❤ by GitHub