先看一个例子：
给出正整数 \(n(n \leq 10^{12})\)，计算：
\[\sum_{i = 1}^n \lfloor \frac{n}{i} \rfloor \]如果直接暴力，复杂度为 \(O(n)\)，无法在 1s 内通过，但使用数论分块（整除分块）可以将复杂度降至 \(O(\sqrt{n})\)。
先看个例子，当 \(n = 100\) 时，\(i\) 和 \(\lfloor \frac{n}{i} \rfloor\) 的情况如下：
| $i \in $ | $\lfloor \frac{n}{i} \rfloor = $ |
|---|---|
| \([1,1]\) | \(100\) |
| \([2,2]\) | \(50\) |
| \([3,3]\) | \(33\) |
| \([4,4]\) | \(25\) |
| \([5,5]\) | \(20\) |
| \([6,6]\) | \(16\) |
| \([7,7]\) | \(14\) |
| \([8,8]\) | \(12\) |
| \([9,9]\) | \(11\) |
| \([10,10]\) | \(10\) |
| \([11,11]\) | \(9\) |
| \([12,12]\) | \(8\) |
| \([13,14]\) | \(7\) |
| \([15,16]\) | \(6\) |
| \([17,20]\) | \(5\) |
| \([21,25]\) | \(4\) |
| \([26,33]\) | \(3\) |
| \([34,50]\) | \(2\) |
| \([51,100]\) | \(1\) |
我们发现，\(\lfloor \frac{n}{i} \rfloor\) 的取值很少，在本例 \(n = 100\) 中只有 \(19\) 种取值。事实上，对于任意 \(n\)，\(\lfloor \frac{n}{i} \rfloor\) 的取值不会超过 \(2 \sqrt{n}\) 种。
有一个显然的结论（结合例子可以理解），所有相等的 \(\lfloor \frac{n}{i} \rfloor\) 对应的 \(i\) 是连续的。因此，我们把这段连续的 \(i\) 作为一个“块”来处理
标签：lfloor,10,12,frac,分块,数论,rfloor,笔记,100 From： https://www.cnblogs.com/5002-qwq/p/18120924