整除分块 | Vozeo's Blog

最近几天在学数论。发现有很多小技巧，比如一些式子的推导变形以及求和。整数分块就是一个小的求和技巧。

大神们的博客讲到在一些数论题里，经常有这样的式子：

$$\sum_{i = 1}^n \left \lfloor \frac{n}{i} \right \rfloor$$

如果用朴素方法，需要$O(n)$的复杂度。

但是可以注意到，由于下取整符号的存在，右边的值只可能有$\sqrt n$种取值，这启发我们用分块的思想，在$O(\sqrt n)$的时间内算出来。

通过打表发现，取值为$\left \lfloor \frac{n}{i} \right \rfloor$的块的右边界为$\frac{n}{\lfloor \frac{n}{i} \rfloor}$，于是就能算出来啦。

~~此处应该有一个证明。~~

for (int l = 1, r; l <= n; l = r + 1) {
	r = n / (n / l);
	sum += (r - l + 1) * (n / l);
	// something else
}