前言
这是一个在数论中很常用的技巧，它通常可以将 $O(n)$ 的时间复杂度优化到大概 $O(\sqrt{n})$ 的复杂度。在这里重点讲述一下关于它的一些性质的证明。
引入
给定一个正数 $n$，求：
$$
\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor
$$
一般我们都会选择 $O(n)$ 的暴力枚举，可如果是 $n \le 10^9$ 的数据范围呢？这么做岂不是会超时？
整除分块就能有效地将该问题进行优化。
证明性质
首先我们可以先让 $n=15$，并暴力打表输出，看看是否可以从中找到一些规律（当然证明是很有必要的，要不然写来干啥呢）。
#include<iostream>
using namespace std;
int n=15;
int main(){
for(int i=1;i<=n;i++){
cout<<i<<' '<<n/i<<endl;
}
}
输出：
i=1: 15
i=2: 7
i=3: 5
i=4: 3
i=5: 3
i=6: 2
i=7: 2
i=8: 1
i=9: 1
i=10: 1
i=11: 1
i=12: 1
i=13: 1
i=14: 1
i=15: 1
打完表后发现输出的值是有规律的，它满足以下性质：
简单一点的性质
-
单调性
这是肯定的，随着 $i$ 的增大，可以明显发现：对于一个 $i$（$i>1$），$\lfloor \dfrac{n}{i} \rfloor$ 的值肯定不大于 $\lfloor \dfrac{n}{i-1} \rfloor$，即整个序列是非严格单调递减的（这应该都知道吧）。 -
分段性
这也是显然的，随着 $i$ 的增大且序列单调不上升，输出的值肯定会变得越来越稠密，自然会形成数值按段分布（显然只有一段）的情况。
较难证明的性质
为方便描述先申明一句，以下的 $\sqrt{n}$ 都是向下取整后的结果。
1.对于任意一个 $n$，$\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor$ 中不同的数值出现的个数是有限的。
那最多出现多少个不同的数呢？这里先给出结论：最多出现 $2 \sqrt{n}$ 个。
我们先把 $1 \dots n$ 分为两段来考虑，即：$\sum_{i=1}^{\sqrt n}$ 与 $\sum_{i= \sqrt{n}+1 }^n$ 两部分。
先考虑第一部分：由于 $1 \dots \sqrt{n}$ 中只有 $\sqrt{n}$ 项，所以该部分最多只出现 $\sqrt{n}$ 个数。
再思考第二部分。虽然 $\sqrt{n}+1 \dots n$ 明显超过 $\sqrt{n}$ 项（如果 $n$ 大点，甚至接近 $n$ 项），但容易发现：$\lfloor \frac{n}{\sqrt{n}+1} \rfloor \le \sqrt{n}$，而 $\lfloor \frac{n}{\sqrt{n}+1} \rfloor = 1$，因此该部分中数值的范围是 $1 \dots \sqrt{n}$，所以该部分不同的数最多也只有 $\sqrt{n}$ 个。
因此整合一下两部分，总的不同的数的个数一定不大于 $2\sqrt{n}$ 个。
得证。（其实也不麻烦对吧）。
2.每一段的边界
这个是最难证明的，也是学习整除分块时的难点。学懂了它也就基本掌握了整除分块的原理。
还是先给出结论：
假设当前块的左端点为 $x$，引入一个函数 $g(x)$ 为当前块的右端点。则根据性质有：$\lfloor \frac{n}{x} \rfloor = \lfloor \frac{n}{g(x)} \rfloor$ 并有 $\lfloor \frac{n}{x} \rfloor > \lfloor \frac{n}{g(x)+1} \rfloor$。则该块的右端点即 $g(x)$ 等于 $\lfloor \frac{n}{\lfloor \frac{n}{x} \rfloor} \rfloor$。
下面的式子有点多，可以耐心地看。
-
证明第一个式子：$\lfloor \frac{n}{x} \rfloor = \lfloor \frac{n}{g(x)} \rfloor$。
先证明 $\lfloor \frac{n}{x} \rfloor \ge \lfloor \frac{n}{g(x)} \rfloor$。
假设将 $g(x)$ 中的下面那个下取整符号删去，即变为：$\lfloor \frac{n}{\frac{n}{x}} \rfloor = x$。因为去掉了下取整符号，所以 $\frac{n}{x} > \lfloor \frac{n}{x} \rfloor$，所以又有：$\lfloor \frac{n}{\lfloor \frac{n}{x} \rfloor} \rfloor > \lfloor \frac{n}{\frac{n}{x}} \rfloor$，所以有： $g(x) \ge x$。则：$\lfloor \frac{n}{x} \rfloor \ge \lfloor \frac{n}{g(x)} \rfloor$。再证明 $\lfloor \frac{n}{x} \rfloor \le \lfloor \frac{n}{g(x)} \rfloor$。
因为 $\lfloor \frac{n}{g(x)} \rfloor = \lfloor \frac{n}{\lfloor \frac{n}{\lfloor \frac{n}{x} \rfloor} \rfloor} \rfloor$，若将 $\lfloor \frac{n}{\lfloor \frac{n}{\lfloor \frac{n}{x} \rfloor} \rfloor} \rfloor$ 中第二小的下取整符号去掉，即变为：$\lfloor \frac{n}{\frac{n}{\lfloor \frac{n}{x} \rfloor}} \rfloor$，可以发现该式因为分母的增大（或不变）而变小了（或不变），并可以化简为：$\lfloor \frac{n}{x} \rfloor$。所以 $\lfloor \frac{n}{\lfloor \frac{n}{\lfloor \frac{n}{x} \rfloor} \rfloor} \rfloor \ge \lfloor \frac{n}{x} \rfloor$，则根据等量代换，可以得到：$\lfloor \frac{n}{g(x)} \rfloor \ge \lfloor \frac{n}{x} \rfloor$。
因此，因为既有 $\lfloor \frac{n}{x} \rfloor \ge \lfloor \frac{n}{g(x)} \rfloor$ 又有 $\lfloor \frac{n}{x} \rfloor \le \lfloor \frac{n}{g(x)} \rfloor$，所以：$\lfloor \frac{n}{x} \rfloor = \lfloor \frac{n}{g(x)} \rfloor$。
得证。
-
再证明第二个式子：$\lfloor \frac{n}{x} \rfloor > \lfloor \frac{n}{g(x)+1} \rfloor$。
这里我们用带余除法来证明（这是在数论中非常常用的证明方式）。设 $n=kx+r$，其中 $k$ 为商，$r$ 为余数，且有 $0 \le r < x$。
所以要证明的这个式子等价于证明：$k> \lfloor \frac{n}{\lfloor \frac{n}{k} \rfloor +1} \rfloor$，也等价于证明：$k(\lfloor \frac{n}{k} \rfloor +1) > n$（令该式为一式）。为证明该式，我们再设 $a=bk+c$，其中 $0 \le c < k$。带回一式有：$k(b+1)>(bk+c)$，化为：$kb+k>bk+c$，则有：$k>c$。因为有 $c<k$，该式成立。因为证得该式等于证明出了 $\lfloor \frac{n}{x} \rfloor > \lfloor \frac{n}{g(x)+1} \rfloor$，所以这个式子也成立。
得证。
因此 $g(x) = \lfloor \frac{n}{\lfloor \frac{n}{x} \rfloor} \rfloor$ 成立，该块的右端的等于该式。
因为之前已经证明出了不同的数的个数最多为 $2 \sqrt{n}$，因此我们枚举的时候可以按照上面证明出的每一块的边界跳着算，时间复杂度也就降为了大约 $O(\sqrt{n})$。
参考代码
#include<iostream>
using namespace std;
int n;
int main(){
long long res=0;
for(int l=1,r;l<=n;l=r+1){
r=n/(n/l);
res+=(long long)(r-l+1)*(n/l);
}
cout<<res;
}
总结
该问题还是比较考数学能力的，并且在莫比乌斯反演、杜教筛等算法中都有运用，需要理解透彻。
