莫比乌斯反演(一):整除分块

莫比乌斯反演(一)

前言

    终于要学莫比乌斯反演啦,封存了半年数论,为了一个星期后的南昌,不得不扩充更广的知识面。遗憾的是,打完南昌可能就要退役了。
    虽然打完南昌一站可能退役了,但是也不能放弃算法的学习。
    (2019-05-26 留)

整除分块

在莫比乌斯反演一类问题中,结果经常会出现形如 $\sum_{i = 1}^{n}{\lfloor\frac{n}{i}\rfloor}$。
如果 $n$ 的范围巨大,暴力 $O(n)$ 的方法可能会超时。而整除分块是 $O(\sqrt{n})$ 的方法。


现在我们要解决一个这样的问题:

解释

参考博客:点击此链接看证明
首先我们可以想到的是 $\sum_{i = 1}^{n}{\lfloor\frac{n}{i}\rfloor}$ 里面,有很多项是重复的。例如在 $n = 10$ 的情况下,$1$ 至 $10$ 项分别是 $10,5,3,2,2,1,1,1,1,1$ 。而整除分块的任务就是 $\sum_{i = 1}^{10}{\lfloor\frac{10}{i}\rfloor} = 10\times1+5\times1+3\times1+2\times2+1\times5$。


$\sum_{i = 1}^{n}{\lfloor\frac{n}{i}\rfloor}$ 的性质:

  1. 不同的项最多只有 $2\sqrt{n}$ 项。
  2. 与 $\lfloor\frac{n}{i}\rfloor$ 相等的最大的 $i’$ 为 $\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$。

代码

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