前言
学习完莫比乌斯反演之后，Caicz 信心满满的打开一道例题，推出例如这样的式子
$$
\sum_{T=1}^{\min(n,m)}\lfloor\frac{n}{T}\rfloor\cdot\lfloor\frac{m}{T}\rfloor(\sum_{k|T，k\in prime}\mu(\frac{T}{k}))
$$
之后，对于每组询问都这样做一遍果断T飞，于是果断点开题解，然后发现了多组求解的科技整除分块
整除分块
一般来说，我们会用到整除分块的形式大概长这样:
$$
\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor
$$
显然的，我们可以 $O(n)$ 快速计算这个式子。但是，有时候在多组询问下， $O(n)$ 解决每组询问也许并不能解决，于是我们就可以通过整除分块 $O(\sqrt{n})$完成每组询问
设 $f(x)=\lfloor\frac{n}{x}\rfloor$ ，则对于 $f(x)$ 我们容易发现它的值是连续且逐步递增的；简单来说即是呈块状分布。同时，我们通过打表等玄学方法可以得到每个块的最后一个数的位置即为 $\large{\frac{n}{\lfloor\frac{n}{i}\rfloor}}$ ,得出结论之后，我们就可以简单的 $O(\sqrt{n})$处理了
for(register int l=1,r;l<=n;l=r+1)
{
r=n/(n/l);
ans+=(r-l+1)*(n/l);
}后记
整除分块单独来说并不难，但是有时候我们推出来的式子还会含有其他的函数，此时我们就需要对这些函数求一个前缀和
当然，在一些难度较高的题目里面，我们甚至难以接受 $O(n)$ 预处理前缀和，这时我们就需要运用杜教筛
