JZTXT

Calculate floor sum

发布时间 2023-08-07 14:33:02作者: SFlyer

problem

不用 ACL！

ll fs(ll n,ll m,ll a,ll b){
	ll res=0;
	if (a>=m){
		res+=n*(n+1)/2*(a/m),a%=m;
	}
	if (b>=m){
		res+=(n+1)*(b/m),b%=m;
	}
	ll c=(a*n+b)/m;
	if (!c){
		return res;
	}
	res+=n*c-fs(c-1,a,m,m-b-1);
	return res;
}