数论分块 学习笔记

数论分块概述

数论分块可以快速计算一些含有除法向下取整的和式（即形如 $\sum _{i=1}^{n}f(i)g(\lfloor {\displaystyle \frac{n}{i}}\rfloor )$ 的和式）。当可以在 $O(1)$ 内计算 $f(r)-f(l)$ 或已经预处理出 $f$ 的前缀和时，数论分块就可以在 $O(\sqrt{n})$ 的时间内计算上述和式的值。

它主要利用了富比尼定理（Fubini's theorem），将 $\lfloor {\displaystyle \frac{n}{i}}\rfloor$ 相同的数打包同时计算。

NOTE

富比尼定理

又称「算两次」，以意大利数学家圭多・富比尼（Guido Fubini）命名。

富比尼定理的积分形式：只要二重积分 $\int \int |f(x,y)|\mathrm{d}x\mathrm{d}y$ 有界，则可以逐次计算二重积分，并且可以交换逐次积分的顺序。

积分号也是特殊的求和号，因此在一般求和中，富比尼定理往往呈现为更换计数顺序，即交换两个求和号。

组合数学中的富比尼定理表现为，用两种不同的方法计算同一个量，从而建立相等关系。

引理 1

$$\mathrm{\forall }a,b,c\in \mathbb{Z},\lfloor \frac{a}{bc}\rfloor =\lfloor \frac{\lfloor \frac{a}{b}\rfloor }{c}\rfloor$$

证：

$$\begin{array}{rl}& \frac{a}{b}=\lfloor \frac{a}{b}\rfloor +r(0\le r<1)\\ ⟹& \lfloor \frac{a}{bc}\rfloor =\lfloor \frac{a}{b}\cdot \frac{1}{c}\rfloor =\lfloor \frac{1}{c}(\lfloor \frac{a}{b}\rfloor +r)\rfloor =\lfloor \frac{\lfloor \frac{a}{b}\rfloor }{c}+\frac{r}{c}\rfloor =\lfloor \frac{\lfloor \frac{a}{b}\rfloor }{c}\rfloor \end{array}$$

证毕

引理 2

$$\mathrm{\forall }n\in {\mathbb{N}}_{+},\left|\{\lfloor \frac{n}{d}\rfloor \mid d\in {\mathbb{N}}_{+},d\le n\}\right|\le \lfloor 2\sqrt{n}\rfloor$$

$|V|$ 表示集合 $V$ 的元素个数

证：

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

对于 $d>\lfloor \sqrt{n}\rfloor$，有 $\lfloor \frac{n}{d}\rfloor \le \lfloor \sqrt{n}\rfloor$，也只有 $\lfloor \sqrt{n}\rfloor$ 种取值

综上，得证

数论分块结论

对于常数 $n$，使得式子

$$\lfloor {\displaystyle \frac{n}{i}}\rfloor =\lfloor {\displaystyle \frac{n}{j}}\rfloor$$

成立且满足 $i\le j\le n$ 的 $j$ 值最大为 $\lfloor {\displaystyle \frac{n}{\lfloor \frac{n}{i}\rfloor }}\rfloor$，即值 $\lfloor {\displaystyle \frac{n}{i}}\rfloor$ 所在块的右端点为 $\lfloor {\displaystyle \frac{n}{\lfloor \frac{n}{i}\rfloor }}\rfloor$。

证明

​ 令 $k=\lfloor {\displaystyle \frac{n}{i}}\rfloor$，可以知道 $k\le {\displaystyle \frac{n}{i}}$。

$$\begin{array}{rl}& \therefore \lfloor {\displaystyle \frac{n}{k}}\rfloor \ge \lfloor {\displaystyle \frac{n}{\frac{n}{i}}}\rfloor =\lfloor i\rfloor =i\\ & \therefore j=max\text{满足条件的所有 }i=i_{max}=\lfloor {\displaystyle \frac{n}{k}}\rfloor =\lfloor {\displaystyle \frac{n}{\lfloor {\displaystyle \frac{n}{i}}\rfloor }}\rfloor \end{array}$$

实现过程

数论分块的过程大概如下：考虑和式

$$\sum _{i=1}^{n}f(i)\lfloor {\displaystyle \frac{n}{i}}\rfloor$$

那么由于我们可以知道 $\lfloor {\displaystyle \frac{n}{i}}\rfloor$ 的值成一个块状分布（就是同样的值都聚集在连续的块中），那么就可以用数论分块加速计算，降低时间复杂度。

利用上述结论，我们先求出 $f(i)$ 的 前缀和（记作 $s(i)=\sum _{j=1}^{i}f(j)$），然后每次以 $[l,r]=[l,\lfloor {\displaystyle \frac{n}{\lfloor \frac{n}{i}\rfloor }}\rfloor ]$ 为一块，分块求出贡献累加到结果中即可。

伪代码如下：

$$\begin{array}{ll}1& \text{Calculate }s(i)\text{, the prefix sum of }f(i)\text{.}\\ 2& l\leftarrow 1\\ 3& r\leftarrow 0\\ 4& \mathit{\text{result}}\leftarrow 0\\ 5& \mathbf{\text{while }}l\le n\mathbf{\text{ do}}:\\ 6& r\leftarrow \lfloor {\displaystyle \frac{n}{\lfloor n/l\rfloor }}\rfloor \\ 7& \mathit{\text{result}}\leftarrow \mathit{\text{result}}+[s(r)-s(l-1)]\times \lfloor {\displaystyle \frac{n}{l}}\rfloor \\ 8& l\leftarrow r+1\\ 9& \mathbf{\text{end while }}\end{array}$$

最终得到的 $result$ 即为所求的和式。

向上取整的数论分块

向上取整与前文所述的向下取整十分类似，但略有区别：

对于常数 $n$，使得式子

$$\lceil {\displaystyle \frac{n}{i}}\rceil =\lceil {\displaystyle \frac{n}{j}}\rceil$$

成立且满足 $i\le j\le n$ 的 $j$ 值最大为 $\lfloor {\displaystyle \frac{n-1}{\lfloor \frac{n-1}{i}\rfloor }}\rfloor$，即值 $\lceil {\displaystyle \frac{n}{i}}\rceil$ 所在块的右端点为 $\lfloor {\displaystyle \frac{n-1}{\lfloor \frac{n-1}{i}\rfloor }}\rfloor$。

证明

​ $\lceil {\displaystyle \frac{n}{i}}\rceil =\lfloor {\displaystyle \frac{n-1}{i}}\rfloor +1$，可以发现 $n$ 的上取整分块与 $n-1$ 的下取整分块是一样的。

WARNING

当 $i=n$ 时，上式会出现分母为 $0$ 的错误，需要特殊处理。

---

N 维数论分块

求含有 $\lfloor {\displaystyle \frac{a_1}{i}}\rfloor$、$\lfloor {\displaystyle \frac{a_2}{i}}\rfloor \cdots \lfloor {\displaystyle \frac{a_n}{i}}\rfloor$ 的和式时，数论分块右端点的表达式从一维的 $\lfloor {\displaystyle \frac{n}{i}}\rfloor$ 变为 $\underset{j=1}{\overset{n}{min}}\{\lfloor {\displaystyle \frac{a_j}{i}}\rfloor \}$，即对于每一个块的右端点取最小（最接近左端点）的那个作为整体的右端点。可以借助下图理解：

一般我们用的较多的是二维形式，此时可将代码中 r = n / (n / i) 替换成 r = min(n / (n / i), m / (m / i))。

---

应用例 1：Chain Reaction

题意

有一排 $n$ 个怪兽，每个怪兽初始血量为 $a_i$，一次攻击会使一段连续的存活的怪兽血量减 $k$，血量不大于 $0$ 视作死亡，对于所有 $k$ 求出击杀所有怪兽所需攻击次数，$n,a_i\le {10}^5$。

思路

太、太、太、太聪明了！！！

对于某个 $k$，使用差分数组的技巧，令 $a_0=0$，答案就是 $\sum _{i=1}^{n}max(0,\lceil {\displaystyle \frac{a_i}{k}}\rceil -\lceil {\displaystyle \frac{a_{i-1}}{k}}\rceil )$。

而如果有 $a_i\ge a_{i-1}$ ，则有 $\lceil {\displaystyle \frac{a_i}{k}}\rceil -\lceil {\displaystyle \frac{a_{i-1}}{k}}\rceil \ge 0$ 。所以可以分别计算 $\lceil {\displaystyle \frac{a_i}{k}}\rceil$ 与 $-\lceil {\displaystyle \frac{a_{i-1}}{k}}\rceil$ 在一段 $k$ 上的贡献，然后差分累加出 $An{s}_i$ 即可。

复杂度 $O(\sum \sqrt{a_i})$。也存在其他解法。

AC 代码

#include <algorithm>
#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>

using namespace std;

mt19937_64 rnd(time(0));

typedef long long ll;
typedef uint64_t ull;

const ll INF = 1e18, Mod = 1e9 + 7;

ll n, m;
ll h[100010];
ll diff[100010];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (ll i = 1; i <= n; i++)
        cin >> h[i], m = max(m, h[i]);

    // cout<<m<<endl;

    for (ll i = 1; i <= n; i++) {
        if (h[i] > h[i - 1]) {
            ll l = 1, r = 0;
            while (l <= h[i]) {
                if (l == h[i]) {
                    diff[l] += 1;
                    break;
                }
                r = min(m, (h[i] - 1) / ((h[i] - 1) / l));

                // cout<<l<<' '<<r<<endl;
                diff[l] += (h[i] + l - 1) / l;
                diff[r + 1] -= (h[i] + l - 1) / l;

                l = r + 1;
            }
            l = 1, r = 0;
            // cout<<l<<' '<<r<<endl;
            while (l <= h[i - 1]) {
                if (l == h[i - 1]) {
                    diff[l] -= 1;
                    break;
                }
                r = min(m, (h[i - 1] - 1) / ((h[i - 1] - 1) / l));

                // cout<<l<<' '<<r<<endl;
                diff[l] -= (h[i - 1] + l - 1) / l;
                diff[r + 1] += (h[i - 1] + l - 1) / l;

                l = r + 1;
            }
        }
    }

    ll ans = 0;
    for (ll i = 1; i <= m; i++) {
        ans += diff[i];
        cout << ans << ' ';
    }
    cout << endl;
    return 0;
}

应用例 2：Monster

思路

枚举 加 k 攻击力 的模块的个数 然后用数论分块来在区间内跳跃遍历答案。

AC 代码

#include <algorithm>
#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
#define OOO cout << ">>>>"; // 调试标识

using namespace std;

mt19937_64 rnd(time(0));

typedef long long ll;
typedef uint64_t ull;

const ll INF = 1e18, Mod = 1e9 + 7;

ll tt;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> tt;

    while (tt--) {
        ll x, y, z, k, ans = INF;
        cin >> x >> y >> z >> k;
        for (ll r = 0;; r++) {
            ll h = z - r * (r + 1) * k / 2, dmg = r * k,
               cost = r * (k * x + y);
            if (h <= 0) {
                ans = min(ans, cost);
                break;
            } else
                for (ll l = max(dmg, 1ll); l <= min(dmg + k, h);) {
                    ans = min(ans, cost + (l - dmg) * x +
                                       (ll)ceil(1.0 * h / l) * y);
                    l = l ^ h ? ((h - 1) / ((h - 1) / l) + 1) : (h + 1);
                }
        }
        cout << ans << endl;
    }
    cout.flush();
    return 0;
}

其中保留了部分调试输出，可以使用它们来查看具体的处理过程，以深化对算法的理解。

数论分块扩展

以计算含有 $\lfloor \sqrt{\frac{n}{d}}\rfloor$ 的和式为例。考虑对于一个正整数 $n$，如何求出集合

$$S=\{\lfloor \sqrt{\frac{n}{d}}\rfloor \mid d\in {\mathbb{N}}_{+},d\le n\}$$

的所有值，以及对每一种值求出哪些 $d$ 会使其取到这个值。可以发现：

1. 因为 $\lfloor \sqrt{\frac{n}{d}}\rfloor$ 是单调不增的，所以对于所有 $v\in S$，使得 $\lfloor \sqrt{\frac{n}{d}}\rfloor =v$ 的 $d$ 必然是一段区间。
2. 对于任意正整数 $t\le n$，我们对 $\le t$ 与 $>t$ 的 $v\in S$ 分别分析，可以发现 $t+n/t^2\ge |S|$，取 $t=\sqrt[3]{n}$ 得到 $|S|$ 的一个上界为 $O(\sqrt[3]{n})$。

这些结论与数论分块所需的引理相似，因此猜测可以写为数论分块形式。

结论是：使得式子

$$\lfloor \sqrt{\frac{n}{p}}\rfloor =\lfloor \sqrt{\frac{n}{q}}\rfloor$$

成立的最大的 $q$ 满足 $p\le q\le n$ 为

$$\lfloor \frac{n}{{\lfloor \sqrt{n/p}\rfloor }^2}\rfloor$$

证明

​ 令 $v=\lfloor \sqrt{{\displaystyle \frac{n}{p}}}\rfloor =\lfloor \sqrt{{\displaystyle \frac{n}{q}}}\rfloor$，那么

$$\begin{array}{rl}v\le \sqrt{{\displaystyle \frac{n}{q}}}& ⟹v^2\le {\displaystyle \frac{n}{q}}\\ & ⟹q\le {\displaystyle \frac{n}{v^2}}\\ & ⟹q\le \lfloor {\displaystyle \frac{n}{v^2}}\rfloor \end{array}$$

同理 $p\le \lfloor n/v^2\rfloor$。同时

$$\lfloor \sqrt{\frac{n}{\lfloor n/v^2\rfloor }}\rfloor \ge \lfloor \sqrt{\frac{n}{n/v^2}}\rfloor =\lfloor v\rfloor =v$$

又由 $p\le \lfloor n/v^2\rfloor$ 以及单调性可推出

$$v=\lfloor \sqrt{\frac{n}{p}}\rfloor \ge \lfloor \sqrt{\frac{n}{\lfloor n/v^2\rfloor }}\rfloor$$

所以

$$\lfloor \sqrt{\frac{n}{\lfloor n/v^2\rfloor }}\rfloor =v$$

进而 $q=\lfloor n/v^2\rfloor$ 是最大的使得 $\lfloor \sqrt{n/p}\rfloor =\lfloor \sqrt{n/q}\rfloor$ 成立的 $q$。

---

故原问题可以写为数论分块形式，代码与数论分块形式并无二异。

两个更加通用的结论

1. 对于某个不超过 $n^{\alpha /\beta }$ 的正整数 $i$，使式子 $\lfloor {\displaystyle \frac{n^{\alpha }}{i^{\beta }}}\rfloor =\lfloor {\displaystyle \frac{n^{\alpha }}{j^{\beta }}}\rfloor$ 成立的最大的 $j$ 为 $\lfloor {\displaystyle \frac{n^{\alpha /\beta }}{{\lfloor n^{\alpha }/i^{\beta }\rfloor }^{1/\beta }}}\rfloor$。
2. 集合 $\{\lfloor {\displaystyle \frac{n^{\alpha }}{d^{\beta }}}\rfloor :d=1,2,\dots ,n\}$ 的大小不超过 $min\{n,2n^{\alpha /(1+\beta )}\}$。

习题

1. CQOI2007 余数求和（需要一点转化和特判）

2. UVa11526 H(n)（几乎可以当做模板题）

3. POI2007 ZAP-Queries（数论分块一般配合 莫比乌斯反演 用以进一步降低复杂度；本题需要用到 $[n=1]=\sum _{d|n}\mu (d)$ 这一条莫反结论）