# 数论-整除分块
这个蒟蒻太蒻了，希望这篇文章能成为自己恶补数论的开始。
**参考资料**
> https://blog.csdn.net/beautiful_CXW/articlehttps://img.qb5200.com/download-x/details/83143756
---
**跳转按钮**
> $\texttt{讲解证明}$
>
> ---
> $\texttt{代码实现}$
>
> ---
> $\texttt{经典例题}$
---
## $\texttt{讲解证明}$
整除分块就是用来求像
$$\sum\limits_{i=1}^n\lfloor \frac{n}{i}\rfloor$$
这样的式子的。
很明显，直接求要 $\Theta(n)$，但是整除分块只需要 $\Theta(\sqrt n)$。
整除分块的第一步是**发现不同的 $\lfloor \frac{n}{i}\rfloor$ 的数量**。
如果 $i\le\sqrt n$：
很明显，因为 $i$ 最多 $\sqrt n$ 种，所以 $\lfloor \frac{n}{i}\rfloor$ 最多 $\sqrt n$ 种。
如果 $i>\sqrt n$：
因为 $\frac{n}{i}<\sqrt n$，所以 $\lfloor \frac{n}{i}\rfloor$ 也不到 $\sqrt n$ 种。
**总结：不同的 $\lfloor \frac{n}{i}\rfloor$ 不到 $2\sqrt n$ 种。**
第二步是计算答案。因为 $f(i)=\lfloor \frac{n}{i}\rfloor$ 的单调性，所以 **$\lfloor \frac{n}{i}\rfloor$ 相同的 $i$ 是相邻的**。
**显而易见的结论：对于 $\lfloor \frac{n}{i}\rfloor=d$，$i\in(\lfloor\frac{n}{d+1}\rfloor,\lfloor\frac{n}{d}\rfloor]$。**
比如 $n=100,d=6$。所以 $i\in(14,16]$
所以可以以 $l=\lfloor\frac{n}{d+1}\rfloor+1,r=\lfloor\frac{n}{d}\rfloor$ 为循环变量，
$$l=\texttt{上一次的}r+1,r=\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor$$
。
---
## $\texttt{代码实现}$
讲解证明一定要仔细看，要不然代码是看不懂的。特短。**必须要全局开 $\texttt{long long}$，这代码可是要过 $n=10^{12}$ 的数据的！**
**code**
```cpp
#include
