参考：

整除分块 - 知乎

董晓算法 G33 整除分块（数论分块）

图都是摘的上面的。

整除分块

整除分块是数论中的一个知识点。一个整除式子在分母不固定的时候，得到的结果也有可能不同，但是因为是整除，所以分母在取连续的值的时候，算出的结果有可能是相同的。比如：

整除分块可以算出每段连续取值区间的左右端点。因为区间个数最多有 $2\ast \sqrt{n}$ 个，从而它可以 $O(\sqrt{n})$ 遍历整除式子的所有取值和取值区间。

分块的性质：

1. 分块的块数 $\le 2\sqrt{n}$（也就是连续的相同取值的区间个数最多只有 $2\sqrt{n}$ 个）。

证明：

向下取整

性质：$i$ 所在块的右端点为 $r=\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor }\rfloor$。

• 证明：
  
  我们通过这个性质可以用区间左端点算出右端点，通过右端点又可以得到下一段区间的左端点，循环下去就可以遍历所有区间（块）了。

code：

for(int l=1,r;l<=n;l=r+1){
	r=n/(n/l);
	...
}

向上取整：

向上取整有两种遍历方式，一个是从前向后（$1\to n$），另一个是从后向前（$n\to 1$）。前者比较符合我们的直观思路，后者和前面的向下取整的过程高度对称，写法比较简洁。先说后者：

从后向前遍历：

性质：$i$ 所在块的左端点为 $l=\lceil \frac{n}{\lceil \frac{n}{i}\rceil }\rceil$。

• 证明是类似的：
  $i$ 所在块的值 $k=\lceil \frac{n}{i}\rceil$，则 $k\ge \frac{n}{i}$，则 $\lceil \frac{n}{k}\rceil \le \lceil \frac{n}{\frac{n}{i}}\rceil =\lceil i\rceil =i$
  所以 $i_{min}=\lceil \frac{n}{k}\rceil =\lceil \frac{n}{\lceil \frac{n}{i}\rceil }\rceil$。代码实现时，左端点 $k=(n+r-1)/r,l=(n+k-1)/k$
  同样的方法进行遍历，不过由于是从右端点算左端点，所以方向变成从后向前遍历了。

code：

for(int l,r=n,k;r>=1;r=l-1){
	k=(n+r-1)/r;
	l=(n+k-1)/k;
	...
}

从前向后遍历：

性质：$i$ 所在块的右端点为 $r=\lfloor \frac{n-1}{\lfloor \frac{n+i-1}{i}\rfloor -1}\rfloor$。

• 证明1：
  $$\begin{array}{c}\{\begin{array}{l}k=\lceil \frac{n}{i}\rceil =\lfloor \frac{n+i-1}{i}\rfloor \\ r=max(i),ik\le n+i-1\end{array}\end{array}\Rightarrow r=\lfloor \frac{n-1}{\lfloor \frac{n+i-1}{i}\rfloor -1}\rfloor$$

• 证明2：
  因为 $k=\lceil \frac{n}{i}\rceil$，所以 $$i(k-1)<n\le ik$$$$\frac{n}{k}\le i<\frac{n}{k-1}$$因为 $i$ 是整数$$\lceil \frac{n}{k}\rceil \le i\le \lfloor \frac{n-1}{k-1}\rfloor$$根据上面的式子，显然 $r=i_{max}=\lfloor \frac{n-1}{k-1}\rfloor =\lfloor \frac{n-1}{\lfloor \frac{n+i-1}{i}\rfloor -1}\rfloor$

code：

for(int l=1,r,k;r<=n;l=r+1){
	k=(n+l-1)/l;
	r=(n-1)/(k-1);
	...
}