数论分块也称整除分块，是一个竞赛中的常用小技巧。
来看一个题目：
已知 f(n) = \sum_{i = 1}^{n} \left \lfloor \frac{n}{i} \right \rfloor，给定一个 n，求 f(n) 的值。
如果 1 \leq n \leq 10^6，直接枚举，时间 5ms。
但是如果 1 \leq n \leq 10 ^ {12} 呢？
现在来介绍数论分块
给出如下表格，枚举 \left \lfloor \frac{n}{i} \right \rfloor:
| $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| $\left \lfloor \frac{n}{i} \right \rfloor$ | 10 | 5 | 3 | 2 | 2 | 1 | 1 | 1 | 1 | 1 |
观察到这个值是逐步变小的，且很多值都相等，这是整除操作的规律。
为了对这些整除的结果进行快速求和，自然能想到把它们分块，其中每块的 \left \lfloor \frac{n}{i} \right \rfloor 相同，将这一块一块一起算，就快多了。
那么问题来到，这个 \left \lfloor \frac{n}{i} \right \rfloor 一共有多少种取值？一共能把他分成多少块？
1)答：分块数小于 2 \sqrt{n} 种。
证明： i \leq \sqrt{n} 时， \frac{n}{i} 的值有 \Big\lbrace {\frac{n}{1},\frac{n}{2},\frac{n}{3},…,\frac{n}{\sqrt{n}}}\Big\rbrace，共 \sqrt{n}个，同理， i \gt \sqrt n时情况一样。所以总个数不超过 2 \sqrt n 个，复杂度为 \mathcal{O}(\sqrt{n})。
2)证明：转自大佬
站内渲染不了，插件还是差点意思（或许版本问题）
Template
ll division_block(ll n){
ll res = 0;
for(ll l = 1, r; l <= n; l = r + 1){
r = n / (n / l);
res += n / l * (r - l + 1);
}
return res;
}