好像只能用来解决一个类似于$\sum^n_{i = 1}\left \lfloor \frac{n}{i} \right \rfloor$这样的整数求和问题，只要是带这个的，那么复杂度最低就能降到根号级别的。
可以发现，比如n = 8这个求和的每一项是这样的

i 1 2 3 4 5 6 7 8
8/i 8 4 2 2 1 1 1 1

那么就可以优化，把结果一样的放在一起分块处理。
分的块大概有$2\sqrt{n}$个，因为当i小于等于$\sqrt{n}$时，取值一共有$\sqrt{n}$种，大于也是一样的

1
2
3
4
5
for (int l = 1; l <= n; ++l) {
	int d = n / l, r = n/d;
	ans += (r-l+1)*d;
	l = r;
}

l和r表示这个区间内的数x除n都是d，即n/x = d，累加即可，复杂度是根号的。

[CQOI2007] 余数求和

给出正整数 $n$ 和 $k$，请计算
$G(n, k) = \sum_{i = 1}^n k \bmod i$
其中 $k\bmod i$ 表示 $k$ 除以 $i$ 的余数。
因为k mod i = k - (k/i)*i,考虑整除分块。因为(k/i)是等于d的，所以在l和r之间是一个等差数列，然后对着等差数列求和即可。
分两种情况，第一种n小于等于k，那就直接做就行。注意r不能大于n，所以还要和n取min。
第二种是n大于k，那么推一下式子：

做法和第一种类似，或者分开看利用最后一个式子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve() {
	int n, k, ans = 0;
	cin >> n >> k;
	if (n <= k) {
		for (int l = 1; l <= n; ++l) {
			int d = k / l, r = min(n, k / d);
			ans += (k - d * l + k - d * r) * (r - l + 1) / 2;
			l = r;
		}
	} else {
		int cnt = 0;
		for (int l = 1; l <= k; ++l) {
			int d = k / l, r = k / d;
			cnt += (k - d * l + k - d * r) * (r - l + 1) / 2;
			l = r;
		}
		ans = cnt + (n - k) * k;
	}
	cout << ans << endl;
}

可能以后学积性函数要用到这个