数论分块可以快速计算一些含有除法向下取整的和式
（即形如 $\sum_{i=1}^nf(i)g(\left\lfloor\dfrac ni\right\rfloor)$ 的和式）
我们可以观察一下$\left\lfloor\dfrac ni\right\rfloor$的值是如何变化的，举个例子$\left\lfloor\dfrac {10}i\right\rfloor$，当$i$从1到10，$\left\lfloor\dfrac {10}i\right\rfloor$的值为 $10,5,3,2,2,1,1,1,1,1$，我们发现，当$i \in [5, 10]$ 时，其值均为 $1$。也就是这一段区间$\left\lfloor\dfrac ni\right\rfloor$ 的值都是相同的。当我们O(n)从 $1$ 到$n$ 枚举 $i$ 时，会发现有很多像上述所说的相同值，能不能将相同的部分一起计算呢？

整除分块可以做到将值相同的区间右端点快速算出，这样对于每一段都能O(1)的算出这一段整体的值。
我们从 $1$ 到 $n$ 枚举 $i$，值为 $\left\lfloor\dfrac ni\right\rfloor$的区间右端点为$\left\lfloor\dfrac n{\lfloor\frac ni\rfloor}\right\rfloor$ 总体时间复杂度$O(\sqrt{n})$
例如上述例子，$\left\lfloor\dfrac {10}i\right\rfloor$，当 $i = 5$ 时，$\left\lfloor\dfrac {10}i\right\rfloor = 2$，$\left\lfloor\dfrac n{\lfloor\frac {10}5\rfloor}\right\rfloor = 10$，能快速的找到值为 $2$ 的区间右端点，这样我们就可以一步到位的计算所有重复值。

时间复杂度证明：
对于值相同的每一段，计算时间复杂度是O(1)的，那么我们的时间复杂度只与段数有关。
当 $\left\lfloor\dfrac ni\right\rfloor \leq \sqrt{n}$ 时，一共 $\sqrt{n}$ 段；
当 $\left\lfloor\dfrac ni\right\rfloor \geq \sqrt{n}$ 时，$i \leq \frac{n}{\sqrt{n}}$ , $i$ 的取值一共 $\sqrt{n}$ 种。
所以总时间复杂度为 $O\sqrt{n}$
代码实现如下

1
2
3
4
5
6
int ans = 0; // 答案
for(int l = 1; l <= n; l++) {
    int r = n / (n / i);    // 区间右端点
    ans += cal(l, r); //计算这一区间的值
    l = r;    // 直接跳到下一个区间
}

题目链接