数论分块

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

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

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

数论分块常与 莫比乌斯反演 等技巧结合使用．

思路

首先，本文通过一个简单的例子来说明数论分块的思路．假设要计算如图所示的双曲线下的整点个数：

这相当于在计算和式：

$$\sum _{i=1}^{11}\lfloor \frac{11}{i}\rfloor .$$

这是前文所示和式在 $f(k)=1,g(k)=k$ 时的特殊情况．

最简单的做法当然是逐列计算然后求和，但是这样需要计算第 $i=1,2,\cdots ,11$ 列中每列整点的个数．观察图示可以发现，这些整点列的可以分成 $5$ 块，每块内点列的高度是一致的，形成一个矩形点阵．所以，只要能够知道这些块的宽度，就能够通过计算这些矩形块的大小快速完成统计．

这就是整除分块的基本思路．

性质

本节讨论关于双曲线 $y=\frac{n}{x}$ 下整点分块的若干结论．具体地，需要将 $1\sim n$ 之间的整数按照 $\lfloor \frac{n}{i}\rfloor$ 的取值分为若干块．设

$$D(n)=\left\{\lfloor \frac{n}{i}\rfloor :1\le i\le n,i\in {\mathbf{N}}_{+}\right\}.$$

这就是 $\lfloor \frac{n}{i}\rfloor$ 所有可能的取值集合．

首先，这样的不同取值只有 $O(\sqrt{n})$ 个．所以，数论分块得到的块的数目只有 $O(\sqrt{n})$ 个．

性质 1

$|D(n)|\le 2\sqrt{n}$．

证明

分两种情况讨论：

• 当 $i\le \sqrt{n}$ 时，$i$ 的取值至多 $\sqrt{n}$ 个，所以 $\lfloor \frac{n}{i}\rfloor$ 的取值也至多只有 $\sqrt{n}$ 个．
• 当 $i>\sqrt{n}$ 时，$\lfloor \frac{n}{i}\rfloor \le \frac{n}{i}<\sqrt{n}$ 也至多只有 $\sqrt{n}$ 个取值．

因此，所有可能取值的总数 $|D(n)|\le 2\sqrt{n}$．

通过更细致的分析，实际上可以精确地描述集合 $D(n)$ 及其大小．

性质 2

设 $s=\lfloor \sqrt{n}\rfloor$．集合 $D(n)$ 中的元素从小到大依次是

$$1<2<\cdots <s-1<s\le \lfloor \frac{n}{s}\rfloor <\lfloor \frac{n}{s-1}\rfloor <\cdots <\lfloor \frac{n}{2}\rfloor <\lfloor \frac{n}{1}\rfloor =n.$$

进而，$|D(n)|=\lfloor \sqrt{4n+1}\rfloor -1$．

证明

首先，对于 $1\le i\le s$，可以证明 $\lfloor \frac{n}{\lfloor n/i\rfloor }\rfloor =i$．令 $d=\lfloor \frac{n}{i}\rfloor$，需要证明 $\lfloor \frac{n}{d}\rfloor =i$．写成不等式，这相当于已知 $d\le \frac{n}{i}<d+1$，需要证明 $i\le \frac{n}{d}<i+1$．已知条件可以写作 $i\le \frac{n}{d}<i+\frac{i}{d}$，因此，只需要证明 $\frac{i}{d}\le 1$，亦即 $i\le d=\lfloor \frac{n}{i}\rfloor$．这等价于 $i\le \frac{n}{i}$，这对于所有 $1\le i\le s\le \sqrt{n}$ 都成立．

这一结果实际上说明，映射 $i\mapsto \lfloor \frac{n}{i}\rfloor$ 构成集合 $\{i:1\le i\le s\}$ 和集合 $\left\{\lfloor \frac{n}{i}\rfloor :1\le i\le s\right\}$ 之间的双射．由于 $i$ 各不相同，$\lfloor \frac{n}{i}\rfloor$ 也各不相同．两个集合唯一有可能相同的元素就是 $s$ 与 $\lfloor \frac{n}{s}\rfloor$．所以，$|D(n)|=2s-\left[s=\lfloor n/s\rfloor \right]$．

要得到 $|D(n)|$ 最终的表达式，需要考察何时 $s=\lfloor \frac{n}{s}\rfloor$ 成立．

• 当 $s=\lfloor \frac{n}{s}\rfloor$ 时，总有 $s\le \frac{n}{s}<s+1$，亦即 $s^2\le n<s^2+s$．此时，有 $4s^2+1\le 4n+1<4s^2+4s+1=(2s+1{)}^2$．又因为 $4n+1$ 一定是奇数，左侧可以等价地松弛到 $4s^2$，所以该条件就等价于 $2s\le \sqrt{4n+1}<2s+1$，亦即 $\lfloor \sqrt{4n+1}\rfloor =2s$．
• 当 $s<\lfloor \frac{n}{s}\rfloor$ 时，总有 $s+1\le \frac{n}{s}$，亦即 $s^2+s\le n$．又因为 $n<(s+1{)}^2$，就有 $s^2+s\le n<(s+1{)}^2$．这就等价于 $(2s+1{)}^2\le 4n+1<4(s+1{)}^2+1$．再次利用 $4n+1$ 是奇数这一点，右侧可以等价地收紧到 $4(s+1{)}^2$，所以该条件就等价于 $2s+1\le \sqrt{4n+1}<2s+2$，亦即 $\lfloor \sqrt{4n+1}\rfloor =2s+1$．

总结这两种情形，就得到 $|D(n)|=\lfloor \sqrt{4n+1}\rfloor -1$ 成立．

然后，单个块的左右端点都很容易确定．

性质 3

对于 $d\in D(n)$，所有满足 $\lfloor \frac{n}{i}\rfloor =d$ 的整数 $i$ 的取值范围为

$$\lfloor \frac{n}{d+1}\rfloor +1\le i\le \lfloor \frac{n}{d}\rfloor .$$

证明

因为 $\lfloor \frac{n}{i}\rfloor =d$ 相当于不等式

$$d\le \frac{n}{i}<d+1.$$

这进一步等价于

$$\frac{n}{d+1}<i\le \frac{n}{d}.$$

利用 $i\in {\mathbf{N}}_{+}$ 这一点，可以对该不等式取整，它就等价于

$$\lfloor \frac{n}{d+1}\rfloor +1\le i\le \lfloor \frac{n}{d}\rfloor .$$

这一性质还体现了图像的对称性：每个块的右端点（前文图中的绿点）的集合恰为 $D(n)$．这很容易理解，因为整个图像关于直线 $y=x$ 是对称的．

除了这些性质外，集合 $D(n)$ 还具有良好的递归性质：

性质 4

对于 $m\in D(n)$，有 $D(m)\subseteq D(n)$．

证明

设 $m=\lfloor \frac{n}{k}\rfloor$，那么，因为对于所有 $i\in {\mathbf{N}}_{+}$，都有

$$\lfloor \frac{m}{i}\rfloor =\lfloor \frac{\lfloor n/k\rfloor }{i}\rfloor =\lfloor \frac{n}{ki}\rfloor \in D(n),$$

所以，$D(m)\subseteq D(n)$．其中，第二个等号用到了 取整函数 关于嵌套分式的性质．

前文已经提到，$D(n)$ 既是每块中 $\lfloor \frac{n}{i}\rfloor$ 的取值集合，也是每块的右端点集合．这意味着，如果要递归地应用数论分块（即函数在 $n$ 处的值依赖于它在 $m\in D(n)\setminus \{n\}$ 处的值），那么在整个计算过程中所涉及的取值集合和右端点集合，其实都是 $D(n)$．一个典型的例子是 杜教筛．

过程

利用上一节叙述的结论，就得到数论分块的具体过程．

为计算和式

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

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

$$\left(\sum _{i=l}^{r}f(i)\right)\cdot g\left(\lfloor \frac{n}{l}\rfloor \right).$$

为了快速计算该和式，通常需要能够快速计算左侧关于 $f$ 的和式．有些时候，该和式的表达式是已知的，可以在 $O(1)$ 时间内完成单次计算；有些时候，可以预处理出它的前缀和，仍然可以在 $O(1)$ 时间内完成单次查询．

在顺次计算每块左右端点时，当前块的左端点 $l$ 就等于前一块的右端点再加 $1$，而当前块的右端点就等于 $\lfloor \frac{n}{\lfloor n/l\rfloor }\rfloor$．由此，可以得到如下伪代码：

$$\begin{array}{l}\text{Algorithm }\text{Sum}(f,g,n):\\ \text{Input. }n,s(k)={\sum }_{i=1}^{k}f(k),g(k).\\ \text{Output. }S(n)={\sum }_{i=1}^{n}f(i)g(\lfloor n/i\rfloor ).\\ \text{Method.}\\ \begin{array}{ll}1& l\leftarrow 1\\ 2& \text{result}\leftarrow 0\\ 3& \text{while }l\le n\text{ do}\\ 4& r\leftarrow \lfloor \frac{n}{\lfloor n/l\rfloor }\rfloor \\ 5& \text{result}\leftarrow \text{result}+(s(r)-s(l-1))\cdot g\left(\lfloor \frac{n}{l}\rfloor \right)\\ 6& l\leftarrow r+1\\ 7& \text{end while}\\ 8& \text{return }\text{result}\end{array}\end{array}$$

假设单次计算 $s(\cdot )$ 的时间复杂度为 $O(1)$，则整个过程的时间复杂度为 $O(\sqrt{n})$．

扩展

前文讨论的是数论分块的最常见也最基本的形式．本节进一步讨论数论分块的扩展形式．

向上取整的数论分块

数论分块可以用于计算含有向上取整的和式：

$$\sum _{i=1}^{n}f(i)g\left(\lceil \frac{n}{i}\rceil \right).$$

因为 $\lceil \frac{n}{i}\rceil =\lfloor \frac{n-1}{i}\rfloor +1$，该和式可以转化为向下取整的情形：

$$f(n)g(1)+\sum _{i=1}^{n-1}f(i)g\left(\lfloor \frac{n-1}{i}\rfloor +1\right).$$

注意到求和的上限发生了变化，以及 $i=n$ 时单独的一项．

多维数论分块

数论分块还可以用于处理包含不只有一个取整式的和式：

$$\sum _{i=1}^{n}f(i)g\left(\lfloor \frac{n_1}{i}\rfloor ,\lfloor \frac{n_2}{i}\rfloor ,\cdots ,\lfloor \frac{n_m}{i}\rfloor \right).$$

为了应用数论分块的思想，需要保证每块中所有取整式 $\lfloor \frac{n_1}{i}\rfloor ,\lfloor \frac{n_2}{i}\rfloor ,\cdots ,\lfloor \frac{n_m}{i}\rfloor$ 的取值都不发生变化，也就是说，多维的块应当是所有一维的块的交集．为此，对于已知的左端点 $l$，相应的右端点为

$$\min \left\{\lfloor \frac{n_1}{\lfloor n_1/l\rfloor }\rfloor ,\lfloor \frac{n_2}{\lfloor n_2/l\rfloor }\rfloor ,\cdots ,\lfloor \frac{n_m}{\lfloor n_m/l\rfloor }\rfloor \right\}.$$

也就是说，对于所有一维分块的右端点取最小值，作为多维分块的右端点．可以借助下图理解：

较为常见的是二维形式，此时可将前述伪代码中 $r\leftarrow \lfloor \frac{n}{\lfloor n/l\rfloor }\rfloor$ 替换成

$$r\leftarrow \min \left\{\lfloor \frac{n_1}{\lfloor n_1/l\rfloor }\rfloor ,\lfloor \frac{n_2}{\lfloor n_2/l\rfloor }\rfloor \right\}.$$

任意指数数论分块

数论分块可以用于含有任意指数的取整式的和式计算：

$$\sum _{i=1}^{\lfloor n^{\alpha /\beta }\rfloor }f(i)g\left(\lfloor \frac{n^{\alpha }}{i^{\beta }}\rfloor \right).$$

其中，$\alpha ,\beta$ 为正实数．本文讨论的基本形式中，$\alpha =\beta =1$．

性质

对于正整数 $n$ 和正实数 $\alpha ,\beta$，设

$$D(n,\alpha ,\beta )=\left\{\lfloor \frac{n^{\alpha }}{i^{\beta }}\rfloor :i=1,2,\cdots ,\lfloor n^{\alpha /\beta }\rfloor \right\}.$$

那么，有

1. $|D(n,\alpha ,\beta )|\le 2n^{\alpha /(1+\beta )}$．

2. 对于 $d\in D(n,\alpha ,\beta )$，使得 $\lfloor \frac{n^{\alpha }}{i^{\beta }}\rfloor =d$ 成立的 $i$ 的取值范围为

   $$\lfloor \frac{n^{\alpha /\beta }}{(d+1{)}^{1/\beta }}\rfloor +1\le i\le \lfloor \frac{n^{\alpha /\beta }}{d^{1/\beta }}\rfloor .$$

证明

对于第一点，分两种情况：

• 当 $i\le \frac{n^{\alpha }}{i^{\beta }}$ 时，有 $i\le n^{\alpha /(1+\beta )}$，所以 $\lfloor \frac{n^{\alpha }}{i^{\beta }}\rfloor$ 至多有 $n^{\alpha /(1+\beta )}$ 种取值．
• 当 $i>\frac{n^{\alpha }}{i^{\beta }}$ 时，有 $i>n^{\alpha /(1+\beta )}$，进而有 $\frac{n^{\alpha }}{i^{\beta }}<n^{\alpha /(1+\beta )}$，所以 $\lfloor \frac{n^{\alpha }}{i^{\beta }}\rfloor$ 也至多只有 $n^{\alpha /(1+\beta )}$ 种取值．

综合两种情形，就有 $|D(n,\alpha ,\beta )|\le 2n^{\alpha /(1+\beta )}$．

对于第二点，$\lfloor \frac{n^{\alpha }}{i^{\beta }}\rfloor =d$ 就等价于

$$d\le \frac{n^{\alpha }}{i^{\beta }}<d+1⟺\frac{n^{\alpha /\beta }}{(d+1{)}^{1/\beta }}<i\le \frac{n^{\alpha /\beta }}{d^{1/\beta }}.$$

对该不等式取整，就得到第二个命题．

利用这些性质，就可以在 $O(n^{\alpha /(1+\beta )})$ 的时间复杂度下实现对任意指数的数论分块．

例子

例如，对于 $\alpha =\beta =1/2$ 时的如下和式

$$\sum _{i=1}^{n}f(i)g\left(\lfloor \sqrt{\frac{n}{i}}\rfloor \right),$$

可以通过数论分块在 $O(n^{1/3})$ 时间内解决．已知块的左端点为 $l$ 时，可以计算右端点为 $r=\lfloor \frac{n}{\lfloor \sqrt{n/l}{\rfloor }^2}\rfloor$．

例题

UVa11526 H(n)

$T$ 组数据，每组一个整数 $n$．对于每组数据，输出 ${\sum }_{i=1}^n\lfloor \frac{n}{i}\rfloor$．

解答

根据前文分析，可以对于每一块相同的 $\lfloor \frac{n}{i}\rfloor$ 一起计算．时间复杂度为 $O(T\sqrt{n})$．

实现

#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;
}

Codeforces 1954E Chain Reaction

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

解答

令 $a_0=0$．假设击杀所有前 $(i-1)$ 只怪兽需要 $T(k,i-1)$ 次攻击，第 $i$ 只怪兽的血量为 $a_i$．由于击杀第 $(i-1)$ 只怪兽时，需要攻击它 $\lceil a_{i-1}/k\rceil$ 次，这些攻击都可以延伸到第 $i$ 只怪兽．因此，要击杀第 $i$ 只怪兽，只需要再攻击 $\max \{0,\lceil a_i/k\rceil -\lceil a_{i-1}/k\rceil \}$ 次．由此，总的攻击次数为

$$T(k,n)=\sum _{i=1}^n\max \left(0,\lceil \frac{a_i}{k}\rceil -\lceil \frac{a_{i-1}}{k}\rceil \right).$$

由于题目涉及的 $n,k$ 都比较大，对每个 $k$ 分别计算该和式并不可行．可以考虑对每个 $i=1,2,\cdots ,n$，都维护数列 $\{T(k,i){\}}_k$．初始时，设 $T(k,0)\equiv 0$．假设数列 $\{T(k,i-1){\}}_k$ 已知，考虑如何对它进行修改才能得到数列 $\{T(k,i){\}}_k$．根据前文分析，只需要对数列的第 $k$ 项增加 $\max \left(0,\lceil \frac{a_i}{k}\rceil -\lceil \frac{a_{i-1}}{k}\rceil \right)$ 即可．利用二维数论分块，可以将这一修改操作拆分成 $O(\sqrt{a_{i-1}}+\sqrt{a_i})$ 段区间修改操作，且每段区间上增加的值是固定的．最后得到的数列 $\{T(k,n){\}}_k$ 就是答案．

由于题目涉及一系列区间加操作，且查询只发生所有修改完成后．所以，可以通过维护差分序列进行区间加修改，最后通过求前缀和得到所求数列．总的时间复杂度为 $O(\sum \sqrt{a_i})$．本题也存在其他解法．

实现

#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;
}

习题

• UVa11526 H(n)
• Luogu P2261 CQOI2007 余数求和
• Luogu P3455 POI2007 ZAP-Queries

参考资料与注释

• 杜教筛的时空复杂度分析 by riteme