P2261 余数求和

题目大意

给出正整数 $n$ 和 $k$，请计算

$$G(n, k) = \sum_{i = 1}^n k \bmod i$$

分析

因为

$$k \bmod i = k - i \left\lfloor \frac{k}{i} \right\rfloor$$

因此有

$$G(n,k) = nk - \sum_{i=1}^n i \left\lfloor \frac{k}{i} \right\rfloor$$

后面需要整数分块。

int main() {
	ll n = rr();
	ll k = rr();
	ll sum = n * k;
	n = min(n, k);
	for (ll l = 1, r; l <= n; l = r + 1) {
		r = min(n, k / (k / l));
		ll t = (l + r) * (r - l + 1) / 2;
		sum -= t * (k / l);
	}
	printf("%lld", sum);
	return 0;
}