数论分块

引入

给定一个正整数 $n$，求解 $$ \sum_{i = n}^{n} \left \lfloor \dfrac{n}{i} \right \rfloor $$ 首先易想到暴力做法，时间复杂度为 $O(n)$，但通过打表 $n = 10$

我们可以发现对于 $i$ 的一段区间 ，$\left \lfloor \dfrac{n}{i} \right \rfloor$ 的值都是相同的。如果我们能一次计算一段的值，那么复杂度将会降低。

分块

设一段的左端点为 $L_{i}$，右端点为 $R_{i}$，则 $L_{i+1} = R_{i} + 1$。如何找到每一段的 $L$ 和 $R$ ？使得 $$ \left \lfloor \dfrac{n}{L} \right \rfloor = \left \lfloor \dfrac{n}{R} \right \rfloor $$ 设 $\left \lfloor \dfrac{n}{L} \right \rfloor = k$，$R = L + d$，得到 $\left \lfloor \dfrac{n}{L+d} \right \rfloor = k$，即 $$ \begin{aligned} n &= Lk + p, \ 0 \leqslant p < L \\ n &= (L + d)k + q, \ 0 \leqslant q < L \end{aligned} $$ 此时 $d_{max} = \left \lfloor \dfrac{p}{k} \right \rfloor$ 带入 $R = L + d$ 得到 $$ \begin{aligned} R &= L + \left \lfloor \dfrac{p}{k} \right \rfloor \\ &= L + \left \lfloor \dfrac{n - Lk}{k} \right \rfloor \\ &= \left \lfloor \frac{n}{\left \lfloor \dfrac{n}{L}\right \rfloor}\right \rfloor \end{aligned} $$ 现在我们已经可以求出每一段分块的区间了，那么每一段的贡献为 $(R−L+1)\times \left \lfloor \dfrac{n}{L}\right \rfloor$

复杂度证明

数论分块的复杂度为 $O(2\sqrt{n})$，我们将证明： $$ \forall n \in \mathbb{N}, \left|\left \lbrace \lfloor \frac{n}{d} \rfloor \mid d \in \mathbb{N},d\leq n \right \rbrace \right| \leq \lfloor 2\sqrt{n} \rfloor $$ $$ \forall n \in N_{+}, \left|\left\{ \lfloor\frac{n}{d}\rfloor\mid d \in N_{+},d\leq n \right\}\right|\leq\lfloor 2\sqrt{n} \rfloor $$

略证：

对于 $d \leqslant \lfloor \sqrt{n} \rfloor$，$\lfloor \frac{n}{d} \rfloor$ 有 $\lfloor \sqrt{n} \rfloor$ 种取值。

对于 $d > \lfloor \sqrt{n} \rfloor$，有$\lfloor \frac{n}{d} \rfloor \leqslant\lfloor \sqrt{n} \rfloor$ ，则也有 $\lfloor \sqrt{n} \rfloor$ 种取值。

练习与思考

P1403 约数研究

求 $\sum_{i=1}^{n}f(i)$，$f(i)$ 代表正数 $i$ 的约数的个数。

思路很简单就是，$1\dots n$ 中间 $i$ 作为约数出现的次数为 $\left \lfloor\dfrac{n}{i} \right \rfloor$

那么答案就是 $$ \sum_{i=1}^{n}\left \lfloor \dfrac{n}{i} \right \rfloor $$

1
2
3
4
5
6
7
8

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

P2424 约数和

题意简单的说就是求 $$ \sum_{i = 1}^{y} f(i) - \sum_{i = 1}^{x} f(i), \ y > x $$ 其中的 $$ f(x) = \sum_{i|x}i $$ 我们要求 $\sum_{i = 1}^{n} f(i)$，也就是求每个约数在 $1\dots n$ 中的出现次数（也就是上题）再乘上约数本身，即 $$ \sum_{i = 1}^{n} i \times \left \lfloor\dfrac{n}{i} \right \rfloor $$ 在上一题的基础上再乘上约数本身，也就是对于每一段 $[L\dots R]$ ，求 $$ \left \lfloor\dfrac{n}{i} \right \rfloor \times \sum_{i = L}^{R} i $$ 由高斯求和得 $$ \left \lfloor\dfrac{n}{i} \right \rfloor \times (L + R) \times (R - L + 1) / 2 $$

1
2
3
4
5
6
7
8

ll solve(int n) {
    ll ans = 0;
    for (ll l = 1, r = 0; l <= n; l = r + 1) {
        r = n / (n / l);
        ans += n / l * (l + r) * (r - l + 1) / 2;
    }
    return ans;
}

类似得题目还有：

P2261 [CQOI2007]余数求和