概论:
数论分块主要用来计算类似于下面的式子:
这类式子经常会在使用莫比乌斯反演的时候见到.
其思路十分简单: 对于一些$i$, $\lfloor \frac{n}{i} \rfloor$的值是相同的, 将这些$i$分段即可加快计算.
对于值$l$, 符合$\lfloor \frac{n}{l} \rfloor = \lfloor \frac{n}{r} \rfloor$的最大的$r=\left\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \right\rfloor$. 所以初始时令$l=1$, 计算出对应的$r$, 然后$l=r+1$迭代即可.
由于$\lfloor \frac{n}{i} \rfloor$单调递减且取值的数量是$O(\sqrt{n})$的, 所以时间复杂度也为$O(\sqrt{n})$.
证明:
若$\lfloor \frac{n}{i} \rfloor = k$, 则有$n = ki + p, p\in[0,n)$.
若$\lfloor \frac{n}{i+d} \rfloor = k$, 则有$n = k(i+d) + p’, p’=p-kd$.
$p’>0$, 所以$d$的最大值$d_m=\lfloor \frac{p}{k} \rfloor$
复杂度证明
对于$i \le \lfloor \sqrt{n} \rfloor$, 最多有$\lfloor \sqrt{n} \rfloor$个$\lfloor \frac{n}{i} \rfloor$的取值.
对于$i > \lfloor \sqrt{n} \rfloor$, $\lfloor \frac{n}{i} \rfloor \le \lfloor \sqrt{n} \rfloor$ 最多有$\lfloor \sqrt{n} \rfloor$个$\lfloor \frac{n}{i} \rfloor$的取值.
所以对于所有$i$, $\lfloor \frac{n}{i} \rfloor$最多有$2\lfloor \sqrt{n} \rfloor$种取值.
One more thing:
有一个结论需要在此证明:
这个结论会在大部分莫比乌斯反演题中出现, 同时也是理解后面的筛法的重要结论.