整除分块 – 小飞侠

整除分块

Post author:xfxia
Post published:2023年10月10日
Post category:其他

转自：

http://www.cnblogs.com/peng-ym/p/8661118.html

前言

最近在学习

莫比乌斯反演

，发现了一个基本上所有的有关

莫比乌斯反演

的题目，都涉及到一个小的知识点：

整除分块

。
所以，在学习莫比乌斯反演之前学会

整除分块

是很有必要的。
那么，我就来介绍一下

整除分块

这一内容

整除分块

可以用到整除分块的形式，大致是这样的：

$\sum_{i=1}^{n}\left \lfloor \frac{n}{i} \right \rfloor$
这个式子，
$O(n)$
计算是非常显然的。但，有的时候因为多组数据的要求，可能
$O(n)$
并不是正确的时间复杂度。那么这个时候，我们就有一种
$O(\sqrt{n})$
的做法。这就是：

整除分块

！
对于每一个
$\left \lfloor \frac{n}{i} \right \rfloor$
我们可以通过打表(或理性的证明)可以发现：有许多
$\left \lfloor \frac{n}{i} \right \rfloor$
的值是一样的，而且它们呈一个块状分布；再通过打表之类的各种方法,我们惊喜的发现对于每一个值相同的块，它的最后一个数就是
$n/(n/i)$
。得出这个结论后，我们就可以做
$O(\sqrt{n})$
的处理了。

附一个整除分块的代码吧：

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

与其他函数的联系

有时候，可能推出来的式子不一定就是一个很裸的整除分块，可能会与某些积性函数相乘，如：μ,φ…… 这时候，我们就需要对这些函数统计一个前缀和。因为，每当我们使用整除分块跳过一个区间的时候，其所对应的函数值也跳过了一个区间。所以此时，就需要乘上那一个区间的函数值。
(当然，如果当出题人想要考考你的数论能力的话，这时就不是统计前缀和这么简单了。可能O(n)线筛都会

TLE

，那么我们就需要

杜教筛

了)