【洛谷P2261】余数求和

题目大意：给定 n, k，求(sumlimits_{i=1}^n k\%n) 的值。

题解：除法分块思想的应用。
(x\%y=x-ylfloor {xover y} floor)，因此只需快速求出 (sumlimits_{i=1}^n {kover i}) 即可。
引理：(iin [1,k], {kover i}) 最多只有不超过 (2sqrt k) 个不同的值。（分情况讨论即可得出）
现在，只需找出每一段的起点和终点即可根据等差数列求和的方式来在 (O(sqrt(n))) 的时间内求得答案。
引理：(iin [x,lfloor k/{lfloor k/x floor} floor]) 时，(k over i) 的值都相等。

代码如下

#include <bits/stdc++.h>
using namespace std;

long long n,k,ans;

int main(){
	scanf("%lld%lld",&n,&k);
	ans=n*k;
	for(int l=1,r;l<=n;l=r+1){
		r=k/l?min(k/(k/l),n):n;
		ans-=(k/l)*(l+r)*(r-l+1)/2;
	}
	printf("%lld
",ans);
	return 0;
}