洛谷 2261 余数求和

注意到$ k mod i = k - lfloor k / i floor $
所以余数求和可以转换成 :

[n * k - sum _ {i = 1} ^ n lfloor k / i floor * i ]

我们发现,在一段连续的 i 的区间上, $ lfloor k / i floor $的值有可能相等,这样可以优化计算
我们的目的就变成寻找这样的区间, 经证明 ([x , k/(k/x))])上, $ lfloor k / i floor $的值是相等的,而且这样的区间最多有 (2 * sqrt n) 个,这样我们就可以遍历每一个区间,用等差数列求和来做

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define ll long long 
using namespace std;
ll n, k, ans;
int main() {
	cin>>n>>k;
	ans = n * k;
	for(ll i = 1, x; i <= n ; i = x + 1) {
		x = k / i ? min(k / (k / i), n) : n;
		ans -= (k / x) * (i + x) * (x - i + 1) / 2;
	}
	cout << ans << endl;
	return 0;
}