数论分块

---

概论:

数论分块主要用来计算类似于下面的式子:

\[ \sum_{i=1}^n f(i)\lfloor \frac{n}{i} \rfloor \]

这类式子经常会在使用莫比乌斯反演的时候见到.

其思路十分简单：对于一些 \(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\)

\[ \begin{aligned} r & = i+d_m \\ & = i+\left\lfloor \frac{n \mod i}{\lfloor \frac{n}{i} \rfloor} \right\rfloor \\ & = \left\lfloor \frac{i \lfloor \frac{n}{i} \rfloor + n-i \lfloor \frac{n}{i} \rfloor}{\lfloor \frac{n}{i} \rfloor} \right\rfloor \\ & = \left\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \right\rfloor \end{aligned} \]

复杂度证明

对于 \(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:

有一个结论需要在此证明:

\[ \left\lfloor \frac{\left\lfloor \frac{n}{a} \right\rfloor}{b} \right\rfloor = \left\lfloor \frac{n}{ab} \right\rfloor \]

这个结论会在大部分莫比乌斯反演题中出现， 同时也是理解后面的筛法的重要结论.

\[ \begin{aligned} \left\lfloor \frac{\left\lfloor \frac{n}{a} \right\rfloor}{b} \right\rfloor & = \left\lfloor \frac{n - n \mod a}{ab} \right\rfloor \\ & > \left\lfloor \frac{n - ab}{ab} \right\rfloor = \left\lfloor \frac{n}{ab} \right\rfloor - 1 \\ \therefore \left\lfloor \frac{\left\lfloor \frac{n}{a} \right\rfloor}{b} \right\rfloor & = \left\lfloor \frac{n}{ab} \right\rfloor \end{aligned} \]