数论分块

数论分块可以快速计算一些含有除法向下取整的和式（即形如 $\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$ 相同的数打包同时计算。

例如这里的双曲线下整点的图片：

图中共分为了 $5$ 块，这 $5$ 块整点的最大纵坐标都相同。如果统计整点的个数，可以从纵向计数改为横向计数，直接计算 $5$ 个矩形即可。

引理 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$ 即为所求的和式。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <iostream>

long long H(int n) {
  long long res = 0;  // 储存结果
  int l = 1, r;       // 块左端点与右端点
  while (l <= n) {
    r = n / (n / l);  // 计算当前块的右端点
    // 累加这一块的贡献到结果中。乘上 1LL 防止溢出
    res += 1LL * (r - l + 1) * (n / l);
    l = r + 1;  // 左端点移到下一块
  }
  return res;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int t, n;
  std::cin >> t;
  while (t--) {
    std::cin >> n;
    std::cout << H(n) << '\n';
  }
  return 0;
}

向上取整的数论分块

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

对于常数 $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$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <algorithm>
#include <iostream>

constexpr int N = 100009;
int n, a[N], maxn;
long long ans[N];

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n;
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
    maxn = std::max(maxn, a[i]);
  }
  for (int i = 0; i < n; ++i)
    for (int l = 1, r;; l = r + 1) {
      r = std::min(l < a[i] ? (a[i] - 1) / ((a[i] - 1) / l) : N,
                   l < a[i + 1] ? (a[i + 1] - 1) / ((a[i + 1] - 1) / l)
                                : N);  // 二维数论分块
      if (r == N) break;
      int x = (a[i + 1] - 1) / l - std::max(a[i] - 1, 0) / l;
      if (x > 0) ans[l] += x, ans[r + 1] -= x;  // 累加贡献
    }
  ++ans[0];  // ⌈a/l⌉=(a-1)/l+1的式子当a=0时不成立，需要修正
  for (int i = 1; i <= maxn; ++i)
    std::cout << (ans[i] += ans[i - 1]) << " \n"[i == maxn];
  return 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))。

数论分块扩展

以计算含有 $\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. CQOI2007 余数求和（需要一点转化和特判）

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

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

本页面最近更新：2025/5/24 12:24:08，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Tiphereth-A, Xeonacid, 2044-space-elevator, 383494, 99-woods, Backl1ght, c-forrest, caijianhong, CCXXXI, ghszt0, Great-designer, iamtwz, ksyx, Marcythm, qwqAutomaton, sshwy, StudyingFather, tder6, TOMWT-qwq, yusancky
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用