数论分块

数论分块可以快速计算一些形如

∑i=1nf(i)g(⌊ni⌋)\sum_{i=1}^nf(i)g(\left \lfloor \frac{n}{i} \right \rfloor )

的和式。如果可以在 O(1)O(1) 时间内计算出 ∑i=lrf(i)\sum_{i=l}^{r}f(i) 或者已经预处理出 ff 的前缀和时，就可以用数论分块在 O(n)O(\sqrt{n}) 时间内计算出上述和式的值。

思路

首先，若计算和式：

∑i=111⌊11i⌋\sum_{i=1}^{11}\left \lfloor \frac{11}{i}\right \rfloor

首先观察到，对于不同的 ii，⌊11i⌋\left \lfloor \frac{11}{i}\right \rfloor 的值有部分相同，呈现出“块状”结构。

i 1 2 3 4 5 6 7 8 9 10 11
⌊11i⌋\left\lfloor \frac{11}{i}\right\rfloor 11 5 3 2 2 1 1 1 1 1 1

假如说我们知道这些块的取值以及宽度，我们就能直接计算每个块的和，快速完成统计。这就是整除分块的基本思路。

性质

下面考虑和式：

∑i=1n⌊ni⌋\sum_{i=1}^{n}\left \lfloor \frac{n}{i}\right \rfloor

我们需要将 1∼n1\sim n 之间的整数按照 ⌊ni⌋\left \lfloor \frac{n}{i}\right \rfloor 的取值分成若干块，设

Dn={⌊ni⌋:1≤i≤n,i∈N+}.D_n=\left \{ \left \lfloor \frac{n}{i}\right \rfloor : 1\le i \le n,i\in \mathbf{N}_+\right \}.

这就是⌊ni⌋\left \lfloor \frac{n}{i}\right \rfloor 所有可能的取值集合。

接下来证明两个性质：

  • ∣Dn∣≤2n\left |D_n \right |\le 2\sqrt{n}

证明：
分两种情况讨论：

  • 当 i≤ni\le \sqrt{n} 时，ii 的取值至多 n\sqrt{n} 个，所以 ⌊ni⌋\left \lfloor \frac{n}{i}\right \rfloor 的取值也至多 n\sqrt{n} 个
  • 当 i>ni>\sqrt{n} 时，⌊ni⌋≤ni<n\left \lfloor \frac{n}{i}\right \rfloor\le \frac{n}{i}<\sqrt{n} 也至多只有 n\sqrt{n} 个取值
  • 对于 d∈Dnd\in D_n，所有满足 ⌊ni⌋=d\left \lfloor \frac{n}{i}\right \rfloor=d 的整数 ii 的取值范围为

⌊nd+1+1⌋≤i≤⌊nd⌋\left \lfloor \frac{n}{d+1}+1\right \rfloor\le i \le \left \lfloor \frac{n}{d}\right \rfloor

证明：
⌊ni⌋=d\left \lfloor \frac{n}{i}\right \rfloor=d 相当于不等式

d≤ni<d+1d\le \frac{n}{i} < d+1

这进一步等价于

nd+1<i≤nd\frac{n}{d+1}<i\le \frac{n}{d}

利用 i∈N+i\in \mathbf{N}_+ 这一点，可以对不等式两边取整，等价于

⌊nd+1⌋+1≤i≤⌊nd⌋\left \lfloor \frac{n}{d+1}\right \rfloor+1\le i\le \left \lfloor \frac{n}{d}\right \rfloor

这一性质体现了图像的对称性：每个块的右端点的集合恰为 DnD_n。

过程

为计算和式：

∑i=1nf(i)g(⌊ni⌋)\sum_{i=1}^nf(i)g(\left \lfloor \frac{n}{i} \right \rfloor )

可以根据 ⌊ni⌋\left \lfloor \frac{n}{i} \right \rfloor 的取值将标号 i=1,2,⋯ ,ni=1,2,\cdots,n 分块，因为 ⌊ni⌋\left \lfloor \frac{n}{i} \right \rfloor 取值相同的标号是一段连续整数 [l,r][l,r]，所以该块中和式的取值为

(∑i=lrf(i))⋅g(⌊nl⌋)(\sum_{i=l}^rf(i))\cdot g(\left \lfloor\frac{n}{l} \right \rfloor)

左侧关于 ff 的和式我们通常可以预处理出它的前缀和，从而在 O(1)O(1) 时间内完成单次查询。

在顺次计算每块的左右端点时，当前块的左端点 ll 就等于前一块的右端点再加1，而当前块的右端点等于 ⌊n⌊n/l⌋⌋\left \lfloor \frac{n}{\left \lfloor n/l \right \rfloor}\right \rfloor，因此，可以顺次计算每个块的值。整个过程的时间复杂度为 O(n)O(\sqrt{n})。

扩展

向上取整的数论分块

对于向上取整的和式：

∑i=1nf(i)g(⌈ni⌉)\sum_{i=1}^nf(i)g(\left \lceil \frac{n}{i} \right \rceil )

可以使用向上取整和向下取整的等式来转化成向下取整的情形：

⌈ni⌉=⌊n+i−1i⌋=⌊n−1i⌋+1\left \lceil \frac{n}{i} \right \rceil=\left \lfloor \frac{n+i-1}{i} \right \rfloor=\left \lfloor \frac{n-1}{i} \right \rfloor+1

∑i=1nf(i)g(⌈ni⌉)=∑i=1n−1f(i)g(⌊n−1i⌋+1)+f(n)g(1)\sum_{i=1}^nf(i)g(\left \lceil \frac{n}{i} \right \rceil )=\sum_{i=1}^{n-1}f(i)g(\left \lfloor \frac{n-1}{i} \right \rfloor+1)+f(n)g(1)

改变求和上限是为了让变形后的式子满足数论分块的形式。