数论分块

很久没有写博文力。

在 2022 年的最后一天发篇博文吧。

何为数论分块？

出现这种式子，直接数论分块：

$\sum\limits_{i = 1}^{n} \left\lfloor\dfrac{n}{i}\right\rfloor$

不难发现朴素的方法是 $\mathcal{O}(n)$。

但这样直接搞是会 van 的。

正确的操作是使用数论分块，达到 $\mathcal{O}(\sqrt{n})$ 的级别。

考虑求和的对象：$\left\lfloor\dfrac{n}{i}\right\rfloor$

我们会发现这个东西是隔一段变化一次的。

毕竟加上了向下取整，相当于是一个整数的运算。

那么寻找这个变化的位置，以这个位置为分界点进行一个分块，每块我们只计算一次，乘上块长就好力。

给一个证明吧：

设左端点为 l，右端点为 r，单点值为 k。

很明显嘛：$k = \left\lfloor\dfrac{n}{l}\right\rfloor = \left\lfloor\dfrac{n}{r}\right\rfloor$

对于 $i \in [l, r]$，r 肯定是所有 i 的最大取值，易得 $i \times k \le n, i \le \dfrac{n}{k}$。

就可以：

$r = \left\lfloor\dfrac{n}{k}\right\rfloor = \left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{l}\right\rfloor}\right\rfloor$

注意！这里不能直接让 r = l！因为这些都是整数下的除法并且加了向下取整！

举个简单的例子：

10 / (10 / 4)

考虑到向下取整，这个得数是 5，如果直接等于过去则会是 4！喜爆。

这样有了左右端点又有了单点值，我想是人就能弄出来了吧：

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

现在您已经入门力！

上点题吧：

UVA11526

原题，但是注意 n = 0 的情况，否则您会当场 RE（。

然后是这个：

P2261

把取模运算换一换，然后拆开算，左边能 $\mathcal{O}(1)$ 解决，右边是一个对于 k 的数论分块，考虑到乘的数不一样，直接换算成平均数乘总个数，做完力。

P3935

考虑如何快速求约数个数。

约数个数无非就是 $\left\lfloor\dfrac{n}{i}\right\rfloor$。

考虑 i 对于每一个倍数都产生贡献，因此每一个 i 的贡献就是 i 的倍数个数。

接一个数论分块，问题解决。