洛谷P2261 [CQOI2007]余数求和

(large{题目链接})
(\)
(Large extbf{Solution: } large{看到这个数据范围线性也跑不过去，所以推测是推式子简化或者能整体求值。\原式可化为ans=sumlimits ^{n}_{i=1}k-lfloordfrac {k}{i} floor imes i = n imes k - sum limits ^ {n} _ {i = 1} lfloordfrac{k}{i} floor imes i。\后面用到了新姿势，除法分块。\思想就是对于lfloordfrac{k}{i} floor值相同的i，合并一起算，由于lfloordfrac{k}{i} floor的取值大约sqrt{k}种，所以时间复杂度为 ext{O}left( sqrt {k} ight)。\下面说一下具体实现，两个变量l和r，表示left[l,r ight]的lfloordfrac{k}{i} floor,i in left[l,r ight]值相等。\l初始值为1，r = Bigglfloordfrac{k}{lfloordfrac{k}{l} floor}Bigg floor，l = r + 1。\感性理解一下为什么这样是对的。})
(\)
(Large extbf{Code: })

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

typedef long long ll;

int main() {
	ios::sync_with_stdio(false);
	ll n, k;
	cin >> n >> k;
	ll l = 1, r, ans = n * k;
	for (; l <= n; l = r + 1) {
		if (k / l) r = min(k / (k / l), n);
		else r = n;
		ans -= (k / l) * (r - l + 1) * (l + r) / 2;
	}
	cout << ans << endl;
	return 0;
}