数论分块

结论

对于固定的 $n$，不同的 $\lfloor \frac{n}{i}\rfloor$ 取值只有 $O(\sqrt{n})$ 个。$\lfloor \frac{n}{i}\rfloor$ 所在的块的右端点为 $\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor }\rfloor$。

IMPORTANT

是 $O(\sqrt{n})$ 个，不是 $\sqrt{n}$ 个！

向下取整模板

for (ll l = 1, r, val; l <= n; l = r + 1) {
    val = n / l;
    r = n / val;
}

向上取整模板

TIP

用式子 $\lceil \frac{n}{i}\rceil =\lfloor \frac{n-1}{i}\rfloor +1$ 可以把向上取整转化为向下取整。相应的，循环里的操作也应该进行这个转化。

for (ll l = 1, r, val; l <= n; l = r + 1) {
    val = (n + l - 1) / l;
    r = val == 1 ? INFLL : (n - 1) / (val - 1);
}