数论分块

数论分块常见形式：

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

发现 \left\lfloor\frac{n}{i}\right\rfloor 只有 \sqrt n 种取值，于是可以每次把相同的值一起计算。

设某一段左端点为 l , 右端点 r=\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor 。

也可以长这样:

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

暴力的想法是对 \frac{n}{i} 做数论分块，但实际上 \left\lfloor\sqrt{\frac{n}{i}}\right\rfloor 的取值更少，于是可以直接对整个做数论分块。

设某一段左端点为 l，对于寻找右端点 r，根据定义，也就是寻找一个最大的 r 使得其 \left\lfloor\sqrt{\frac{n}{r}}\right\rfloor 的值与 l 处相等。

所以也就是解 \left\lfloor\sqrt{\frac{n}{l-1}}\right\rfloor < \left\lfloor\sqrt{\frac{n}{r}}\right\rfloor \leq \left\lfloor\sqrt{\frac{n}{l}}\right\rfloor

因为左右边已知，也就是解一个关于 r 的不等式，然后就做完了。

以后值不多且连续的套数论分块就更灵活了，虽然以前一直以为只有整除才能做。