数论-整除分块

# 数论-整除分块 这个蒟蒻太蒻了，希望这篇文章能成为自己恶补数论的开始。 **参考资料** > 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