整除分块，是指对$\left\lfloor \frac{n}{i}\right\rfloor$的相同的数之间进行分类的方法。其实分块是指连续形式的分类方法，换句话说是给定区间的分类，其对应的另一个技术叫筛法，筛法是不限于连续形式，而是在一个范围内进行分类的方法。这是两种在数学上分类方法的区别。而整除分块又是特指对$\left\lfloor \frac{n}{i}\right\rfloor$形式的分块。因此，这是一个目的十分明确的技术。

首先以$n=20$为例，举例不同$i$下，$\left\lfloor \frac{n}{i}\right\rfloor$的结果：

$i$	$\left\lfloor \frac{n}{i}\right\rfloor$
1	20
2	10
3	6
4	5
5	4
6	3
7	2
8
9
10
11	1
12
13
14
15
16
17
18
19
20

可以看见，不变的一块的长度越来越大。这只是一个例子，直观了解什么是整除分块，以及其必要性。下面来正式说明整除分块：

定理：给定$n$，对于不同$i$而言，令$i_k$为恰为$\left\lfloor \frac{n}{i}\right\rfloor$发生变化的位置。那么有:

$$i_{k+1}=\left\lfloor n/{\left\lfloor n/i_k \right\rfloor }\right\rfloor+1 $$

证明:

对于给定的$\left\lfloor\frac{n}{i+di}\right\rfloor=k$，则$ki+r=n=k(i+di)+r^\prime$。

有$n=ki+kdi+r^\prime$，即$r=kdi+r^\prime$，由$r^\prime\geq0\Rightarrow r-kdi=r^\prime\geq0$，得到$di\le\frac{r}{k}$

注意整数关系，必有$di\le\lfloor\frac{r}{k}\rfloor$，也即$di$的最大值为$\lfloor\frac{r}{k}\rfloor$。

那么保持$k$不变的上限为$i+{\rm di}_{max}=i+\left\lfloor\frac{r}{k}\right\rfloor=\left\lfloor i+\frac{n-ki}{k}\right\rfloor=\left\lfloor\frac{n-ki+ki}{k}\right\rfloor=\left\lfloor\frac{n}{k}\right\rfloor=\lfloor n/{\lfloor n/i \rfloor}\rfloor$。

故$i_{k+1}=\left\lfloor n/{\left\lfloor n/i_k \right\rfloor }\right\rfloor+1$恰好为下一个变化的位置。

证明可以不看，主要的思想是源于除法结构的最值讨论。可以说，根本的原因是余数的最值规律。因此，光观察而尝试得出结论是十分困难的，这个只能是记忆，或者尝试理解证明过程。在此就并不推荐纯计算机方向的acmer参与，而acm-mather则应该了解证明。

因此使用R = n/(n/L) + 1来表示下一头端点就是整除分块的根本目的。有且只需记住这样操作即可。

实际上的整除分块的复杂度是$O\left(\sqrt{N}\right)$因此一般数据范围是$10^9$以内。