数论分块

· · 算法·理论

数论分块常见形式:

\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 的不等式,然后就做完了。

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