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

莫比乌斯反演(一)

前言

    终于要学莫比乌斯反演啦，封存了半年数论，为了一个星期后的南昌，不得不扩充更广的知识面。遗憾的是，打完南昌可能就要退役了。     虽然打完南昌一站可能退役了，但是也不能放弃算法的学习。 (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\le 10^{12})$$

解释

参考博客:点击此链接看证明 首先我们可以想到的是 ${\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\times 1+5\times 1+3\times 1+2\times 2+1\times 5$。

${\sum }_{i=1}^n\lfloor \frac{n}{i}\rfloor$ 的性质：

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

代码

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