亲宝软件园·资讯

展开

数论-整除分块

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

加载全部内容

相关教程
猜你喜欢
用户评论