数论函数与筛法 (Part 1)

Alex_Wei · 2026-03-06 09:25:30 · 算法·理论

Part 2 还在施工 & 会补充一些困难的莫反题目。欢迎捉虫或提供好题。

洛谷 & cnblogs

本篇笔记介绍了数论函数和筛法相关的知识点。部分定义和记号见 同余理论。

定义与记号

• 数论函数：定义域为正整数的函数称为 数论函数，可以看成数列。常见数论函数的值域为整数。
• 加性函数：若对任意 a, b\in \mathbb{N} ^ + 且 a\perp b，均有 f(ab) = f(a) + f(b)，则称 f 为 加性函数。注意区分数论的加性函数和代数的加性函数 f(a + b) = f(a) + f(b)。
• 积性函数：若对任意 a, b\in \mathbb{N} ^ + 且 a\perp b，均有 f(ab) = f(a)f(b)，则称 f 为 积性函数。f(1) = 1 是必要条件。
• 完全积性函数：若对任意 a, b\in \mathbb{N} ^ {+}，均有 f(ab) = f(a)f(b)，则称 f 为 完全积性函数。完全积性函数是积性函数。
• 数论函数的 加法：对数论函数 f, g，f + g 表示 f 和 g 的对应位置相加，即 (f + g)(x) = f(x) + g(x)。
• 数论函数的 数乘：对数 c 和数论函数 f，c\cdot f 表示 f 的各个位置乘 c，即 (c\cdot f)(x) = c \cdot f(x)。一般记为 cf。积性函数的数乘不是积性函数（考虑 f(1) = 1 的必要条件）。
• 数论函数的 点乘：对数论函数 f, g，f \cdot g 表示 f 和 g 的对应位置相乘，即 (f \cdot g)(x) = f(x)g(x)。一般记为 fg。两个积性函数的点乘是积性函数。

积性函数是这篇博客的主角。为什么它如此重要呢？因为积性函数由它在质数幂处的取值完全确定。给定 n，计算 n 在唯一分解下每个质数幂处 f 的取值，就能得到 f(n)。

关于常见积性函数，见 2.2 小节。

积性函数的性质在数论函数和质因数分解之间建立了桥梁，于是很多积性函数的筛法都和质因数分解当中最基本的元素——质数息息相关。因此，我们首先需要学习质数筛法。

1. 质数筛法

质数筛法是数论函数体系当中最基本的知识点，也是大部分数论题目所必需的算法。

质数判定的基本想法是寻找合数满足的性质，并证明质数不满足这些性质。从合数满足的性质出发，得到判定合数的必要条件（取否定，即判定质数的充分条件），再考虑证明其充分性。

关于更快速的质数判定，见质因数分解笔记的 Miller-Rabin。

1.1 基本算法

1.1.1 试除法

判定 n 是不是质数。

如果 n 是合数，那么存在因数 d\in [2, n - 1]。如果 d \geq \sqrt n，那么 n / d 也是非平凡因数且 n / d \leq \sqrt n。

因此，如果 n 是合数，那么存在因数 d\in [2, \sqrt n]。反过来，如果存在这样的 d，那么 n 显然是合数。

时间 \mathcal{O}(\sqrt n)。

1.1.2 倍数筛

判定 2 到 n 的每个数是不是质数。

如果直接对每个数使用试除法，则时间复杂度 \mathcal{O}(n\sqrt n)。

我们希望找到因数-倍数关系判定质数。试除法的问题在于，对于每个倍数，难以快速求出其所有因数，导致枚举了太多不是因数的数。但对于一个因数，我们很容易找到其所有倍数。这引出了接下来的倍数筛。

如果 x 是合数，那么存在非平凡因数 d。相反，如果 x 是质数，那么不存在这样的 d。

如果 d\in [2, x - 1] 是 x 的因数，那么存在 k > 1 使得 x = kd。于是，我们用一个数的不是它自己的倍数标记出合数。

枚举 2\sim n 的所有数 x，并将 2x, 3x, \cdots 标记为合数，直到 kx > n。过程结束后没有被标记的数就是质数。

时间 \mathcal{O}(\sum_{i = 1} ^ n n / i) = \mathcal{O}(n\ln n)。

1.1.3 区间筛

判断 l 到 r 的每个数是不是质数。

在倍数筛的过程中，如果 x 有非平凡因数 d，那么 d 和 x / d 一定有一个不超过 \sqrt x。因此，仅使用 [2, \sqrt x] 筛去所有合数即可。

推广到本题，就是仅使用 [2, \sqrt r] 的每个数标记 l, r 之间的合数。

时间 \mathcal{O}((r - l)\ln r + \sqrt r)。

1.2 埃氏筛

判定 2 到 n 的每个数是不是质数。

由算术基本定理，如果 x 是合数，那么存在 质因数 d\in [2, x - 1]。相反，如果 x 是质数，那么不存在这样的 d。基于此，埃氏筛用 已经筛出的质数 的倍数标记合数。

• 算法流程：从 2 到 n 枚举所有数 x。若 x 没有被标记，则 x 是质数，并将 x 的除了本身的倍数标记为合数。
• 小优化：因为合数的最小质因数不超过其平方根，所以我们可以从 x ^ 2 开始标记，不影响复杂度。这个思想很重要，因为外层只需枚举到 \sqrt n。埃氏筛提供了亚线性计算特殊积性函数的框架：考虑如何在每一轮中加入新标记的合数的贡献。

代码如下：

for(int i = 2; i < N; i++) {
  if(!vis[i]) {
    pr[++cnt] = i;
    for(int j = i + i; j < N; j += i) vis[j] = 1;
  }
}

复杂度证明

结论（质数倒数和的数量级）

不超过 n 的质数的倒数之和是 \mathcal{O}(\log\log n)。

证明

每个数只会被其质因数标记到，所以

\sum_{p\in \mathbb{P},\ p\leq n} \frac n p = \sum_{p\in \mathbb{P},\ p\leq n} \left(\left\lfloor\frac n p\right\rfloor + \mathcal{O}(1)\right) = \sum_{i = 1} ^ n \omega(i) + \mathcal{O}(n),

即

\sum_{p\in \mathbb{P},\ p\leq n} \frac 1 p = \frac 1 n \sum_{i = 1} ^ n \omega(i) + \mathcal{O}(1).

根据 d(i) 的计算式，

\sum_{i = 1} ^ n 2 ^ {\omega(i)} \leq \sum_{i = 1} ^ n d(i) = \mathcal{O}(n\log n).

根据 2 ^ x 的凸性和 Jensen 不等式（琴生不等式），得

2 ^ {\frac{\sum_{i = 1} ^ n \omega(i)} n} \leq\frac 1 n\sum_{i = 1} ^ n 2 ^ {\omega(i)} = \mathcal{O}(\log n).

取对数，

\sum_{p\in \mathbb{P},\ p\leq n} \frac 1 p = \frac 1 n \sum_{i = 1} ^ n \omega(i) + \mathcal{O}(1) = \mathcal{O}(\log \log n). \square

因此，埃氏筛的时间为 \mathcal{O}(n\log\log n)。

1.3 线性筛

线性筛也称欧拉 Euler 筛。

埃氏筛用质数的倍数筛去合数，导致一个合数会被它的多个质因数筛到。如果让每个合数只被筛一次，就可以做到线性了。

考虑用每个合数的 最小质因数 筛去它。设当前筛到 i，有两种思路：

• 一是当 i 是质数时，筛去最小质因数是 i 的合数，即求出所有 j 使得 ij 的最小质因数为 i。这要求 j 的最小质因数不小于 i，也就是当前还没有被标记的所有数。可以用链表维护，但是较麻烦。
• 二是对每个 i，筛去除掉最小质因数 j 之后的值等于 i 的合数。这要求 j 不大于 i 的最小质因数，因此 j 只能是所有不大于 i 的最小质因数的质数。从小到大枚举质数 j，直到 j 等于 i 的最小质因数时退出，判定条件是 j\mid i。

显然采用第二种思路。

另一种理解方式是，对于每个 i，设其最小质因数为 p，则对于不大于 p 的质数 q，iq 的最小质因数为 q。将所有 iq 标记为合数，则每个合数 c 仅在 i = c / q 时以 iq 的形式被删去，其中 q 是 c 的最小质因数。

综上，得到如下算法。从 2 到 n 枚举 i：

• 若 i 没有被标记，则 i 是素数。

• 从小到大遍历当前筛出的所有素数 pr_j，要求 i\cdot pr_j 的最小质因数为 pr_j。将 i\cdot pr_j 标记为合数。

• 若 pr_j\mid i，则退出遍历。再往下枚举，对应的最小质因数就不是我们想要的了：因为 pr_j\mid i，所以对于 k > j，pr_j \mid i\cdot pr_k。i\cdot pr_k 的最小质因数是 pr_j，而非 pr_k。

时间 \mathcal{O}(n)。模板题 代码。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e8 + 5;
bool vis[N];
int n, q, pr[N / 16], cnt;
int main() {
  cin >> n;
  for(int i = 2; i <= n; i++) {
    if(!vis[i]) pr[++cnt] = i;
    for(int j = 1; j <= cnt && i * pr[j] <= n; j++) {
      vis[i * pr[j]] = 1;
      if(i % pr[j] == 0) break;
    }
  }
  cin >> q;
  while(q--) {
    int x;
    scanf("%d", &x);
    printf("%d\n", pr[x]);
  }
  return 0;
}

1.4 线性筛积性函数

线性筛提供了在线性时间内筛出具有特殊性质的 积性函数 在 1\sim n 处所有取值的基本框架。

只要可以在 \mathcal{O}(1) 时间内计算积性函数 f 在任意质数幂处的取值 f(p ^ k)，就可以线性筛出 f 在 1\sim n 处的所有取值。

注意：这只是 f 可线性筛的充分条件。存在更弱的条件使得 f 可线性筛，见 2.2 小节。

根据积性函数的性质，考虑求出 l_i 表示 i 的最小质因数 p 的最高次幂 p ^ {\nu_p(i)}。若 i 是质数幂，则直接计算，否则 l_i\neq i，f(i) = f(l_i) f(i / l_i)。

for(int i = 2; i < N; i++) {
  if(!vis[i]) pr[++cnt] = i, f[i] = ..., low[i] = i; // 单独算 f(p)
  for(int j = 1; j <= cnt && i * pr[j] < N; j++) {
    vis[i * pr[j]] = 1;
    if(i % pr[j] == 0) { // i 与 p 不互质
      low[i * pr[j]] = low[i] * pr[j];
      if(i == low[i]) f[i * pr[j]] = ...; // i = p ^ k，单独算 f(p ^ {k + 1})
      else f[i * pr[j]] = f[i / low[i]] * f[low[i * pr[j]]];
      break;
    }
    low[i * pr[j]] = pr[j];
    f[i * pr[j]] = f[i] * f[pr[j]]; // i 与 p 互质，f(ip) = f(i) * f(p) 
  }
}

2. 狄利克雷卷积

狄利克雷 Dirichlet 卷积是数论函数的基本运算。

2.1 定义

我们知道加法卷积

但加法卷积不保留积性。将加法换成乘法，结果如何？

称为 狄利克雷卷积，记为 h = f * g。按照定义式计算狄利克雷卷积，时间为调和级数的 \mathcal{O}(n\log n)。

狄利克雷卷积的另一种更常见的形式为

2.2 常见数论函数

设 n 的唯一分解为 \prod_{i = 1} ^ m p_i ^ {c_i}，以下列出了一些常见的积性函数。除了 \omega 是加性函数以外，其余所有函数都是积性函数。

单位函数

当 n = 1 时取值为 1，否则为 0。

单位函数 \epsilon 是狄利克雷卷积的单位元。

常数函数

所有位置的取值均为 1。

一个函数和常数函数的狄利克雷卷积称为狄利克雷前缀和，其结果函数在 n 处的取值为原函数在 n 的所有因数处的取值和。

恒等函数

所有位置的取值均为本身。更一般地，

除数函数

性质 1.2（结合律）

狄利克雷卷积有 结合律。

证明

\begin{aligned} ((f * g) * h)(n) & = \sum_{dd'd'' = n} f(d) g(d') h(d''). \end{aligned} d, d', d''$ 的地位相同。先结合 $d'$ 和 $d''$，可知 $(f * g) * h = f * (g * h)$。$\square

性质 1.3（分配律）

狄利克雷卷积有 分配律。

证明

\begin{aligned} ((f + g) * h)(n) & = \sum_{dd' = n} (f(d) + g(d)) h(d') \\ & = \sum_{dd' = n} f(d)h(d') + \sum_{dd' = n} g(d)h(d') \\ & = (f * h + g * h)(n). \end{aligned}

因此 (f + g) * h = f * h + g * h。\square

注意：点积和狄利克雷卷积之间不具有交换律。(f\cdot g) * h \neq (f * h) \cdot g。

考察卷积的单位元。容易发现：

性质 2（单位元）

**证明** 考虑 $(\epsilon * f)(n)$ 的计算式，只有 $f(n)$ 这一项非零。所以 $(\epsilon * f)(n) = f(n)$。$\square

单位函数 \epsilon 是狄利克雷卷积的 单位元。这也是其名称的由来。

在单位元的基础上，定义狄利克雷卷积的逆元 f ^ {-1}，满足 f * f ^ {-1} = f ^ {-1} * f = \epsilon。

性质 3（逆元）

**证明** 设 $g = f ^ {-1}$。 - 当 $f(1) = 0$ 时，$f(1)g(1) = 0\neq \epsilon(1)$。所以无论如何 $g$ 都不存在。 - 当 $f(1) \neq 0$ 时，$g(1) = \frac 1 {f(1)}$。 对于 $n > 1$，通过 $\sum_{d\mid n} g(d)f(n / d) = 0$ 得到递推式 $$ g(n) = -\frac{\sum_{d \mid n \land d \neq n} g(d)f(n / d)} {f(1)}. $$ 这同时说明了 **逆元唯一**。$\square

计算逆元的时间也是 \mathcal{O}(n\log n)。

性质 3 说明只要 g(1) \neq 0，就可以计算除法 f * g ^ {-1}。

性质 4（消去律）

**证明** **充分性**：$f * h = g * h\implies f * h * h ^ {-1} = g * h * h ^ {-1} \implies f = g$。 **必要性**：$f = g\implies f * \epsilon = g * \epsilon$。$\square

等式两侧同时卷相同的可逆数论函数，等式仍然成立。

性质 5（乘法保留积性）

积性函数的狄利克雷卷积是积性函数。

证明

考虑积性函数 f 和 g 的狄利克雷卷积 h。

若 n\perp m，则对于任意 d_1\mid n 和 d_2\mid m，d_1\perp d_2。因此，

\begin{aligned} h(n)h(m) & = \left(\sum_{d_1d_1' = n} f(d_1) g(d_1' )\right)\left(\sum_{d_2d_2' = m} f(d_2) g(d_2')\right) \\ & = \sum_{dd' = nm} f(d) g(d') & (d = d_1d_2) \\ & = h(nm). \end{aligned}

第二步用到了两个条件：

\square

性质 5 很重要。它说明 狄利克雷卷积保留积性。

性质 6（除法保留积性）

积性函数的狄利克雷卷积逆元是积性函数。

证明

证明来自 OI-Wiki。

设 g = f ^ {-1}。回忆积性函数 f 一定满足 f(1) = 1。

根据 f 的积性可知 g(1) = \frac 1 {f(1)} = 1，所以 g(n) = g(1) g(n)。

考虑数学归纳法。对 nm 的大小归纳。

对于 n, m > 1 且 n\perp m，假设对任意 xy < nm 且 x\perp y，均有 g(xy) = g(x)g(y)。

当 n = 1 或 m = 1 时，命题显然成立。因此，只需证明 g(nm) = g(n)g(m)。

\begin{aligned} g(nm) & = -\sum_{d d' = nm\land d\neq nm} g(d)f(d') \\ & = -\sum_{d_1d_1' = n\land d_2d_2' = m\land d_1d_2 \neq nm} g(d_1) g(d_2) f(d_1')f(d_2') \\ & = f(1) ^ 2 g(n) g(m) -\sum_{d_1d_1' = n \land d_2d_2' = m} g(d_1) g(d_2) f(d_1') f(d_2') \\ & = g(n)g(m) - \left(\sum_{d_1d_1' = n} g(d_1) f(d_1')\right) \left( \sum_{d_2d_2' = m} g(d_2) f(d_2')\right) \\ & = g(n)g(m) - \epsilon(n) - \epsilon(m) \\ & = g(n)g(m). \end{aligned}

最后一步的依据是 n, m > 1。\square

性质 5 和性质 6 告诉我们：积性函数的狄利克雷卷积与狄利克雷卷积逆是积性函数。

注意：积性函数的和与差不是积性函数。

2.4 线性筛狄利克雷卷积

根据积性函数的狄利克雷卷积是积性函数的结论，考虑使用线性筛筛出 h = f * g，其中 f, g 是积性函数。

写出 h 的表达式：

其中 p 是质数，k 是正整数。

对于第一种情况和第三种情况，使用 1.4 线性筛积性函数的技巧直接计算。

关键在于第二种情况。若已知 f, g 在质数幂处的取值，则需要 \mathcal{O}(k) 的时间。

• 当 f 是完全积性函数时，h(p ^ k) = f(p)h(p ^ {k - 1}) + g(p ^ k)，可以 \mathcal{O}(1) 计算。对于 g 同理。

尝试估计第二种情况的复杂度 T(n)。证明来自 EI。

所有不大于 \sqrt[k] n 的质数产生 \mathcal{O}(k) 的贡献，因此

T(n) = \sum_{x = 1} ^ {\log n} x\pi(\lfloor\sqrt[x]n\rfloor) \approx \sum_{x = 1} ^ {\log n} \frac {x\sqrt[x] n}{\ln \sqrt[x] n} = \frac 1 {\ln n} \sum\limits_{x = 1} ^ {\log n} x ^ 2\sqrt[x] n.

当 x = 1 时，x ^ 2\sqrt[x] {n} = n。

当 2\leq x\leq \log n 时，因为 x ^ 2 递增，\sqrt [x] {n} 递减，所以

x ^ 2\sqrt[x]{n} \leq (\log_2 ^ 2 n) \cdot\sqrt n = \mathcal{O}(n).

因此

T(n) = \frac 1 {\ln n} \sum_{i = 1} ^ {\log_2 n} \mathcal{O}(n) = \mathcal{O}(n).

使用线性筛求出两个 在质数幂处取值已知 的积性函数的狄利克雷卷积在 1\sim n 处的取值的时间复杂度为 \mathcal{O}(n)。这给出了积性函数可线性筛的更弱条件：在 \mathcal{O}(k) 的时间内计算质数幂处的取值。

2.5 狄利克雷前缀和

前置知识：高维前缀和。

任意数论函数 f 与常数函数 1 卷积得到 g。称 g = f * 1 为 f 的 狄利克雷前缀和，则

狄利克雷前缀和用途广泛，因为对每个 n 计算给定数论函数在其所有因数处的取值之和有良好的实际含义。其逆运算为狄利克雷差分，相当于 f * \mu，将在第四章介绍。

将正整数 n 写成无穷序列 a_n = \{c_1, c_2, \cdots, c_i, \cdots\}，表示 n = \prod p_i ^ {c_i}，其中 p_i 为第 i 个质数。因为 x\mid y 等价于 x 的每个质因数的幂次不大于 y 的该质因数的幂次，即 \forall i, a_x(i) \leq a_y(i)，那么 n 的所有因数就是所有使得 0\leq a_d(i) \leq a_n(i) 的 d。

• 以上分析结合乘法原理和唯一分解定理可以推出因数个数公式 d(n) = \prod (c_i + 1)。

因此，f * 1 可以看成对下标做关于其无穷序列的高维前缀和，即

根据高维前缀和，枚举每一维并将所有下标关于该维做前缀和，得到狄利克雷前缀和算法：

• 初始令 x_i = f(i)。
• 按任意顺序枚举每个维度，即按任意顺序枚举不超过 n 的质数 p_i。
• 按当前维度从小到大的顺序，将每个下标贡献至当前维度加 1 之后的对应下标，即从小到大枚举 k\in [1, \frac n {p_i}]，将 x_{p_ik} 加上 x_k。
• 最终 x 即为 g。

因为小于 n 的素数倒数和为 \mathcal{O}(\log\log n)，所以算法时间 \mathcal{O}(n\log\log n)。

模板题 代码。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e7 + 5;
int n;
unsigned ans, a[N], seed;
inline unsigned rd() {
  seed ^= seed << 13, seed ^= seed >> 17, seed ^= seed << 5;
  return seed;
}
bool vis[N];
int cnt, pr[N >> 3];
void sieve() {
  for(int i = 2; i <= n; i++) {
    if(!vis[i]) pr[++cnt] = i;
    for(int j = 1; j <= cnt && i * pr[j] <= n; j++) {
      vis[i * pr[j]] = 1;
      if(i % pr[j] == 0) break;
    }
  }
}
int main() {
  cin >> n >> seed, sieve();
  for(int i = 1; i <= n; i++) a[i] = rd();
  for(int i = 1; i <= cnt; i++) {
    for(int j = 1; j * pr[i] <= n; j++) {
      a[j * pr[i]] += a[j];
    }
  }
  for(int i = 1; i <= n; i++) ans ^= a[i];
  cout << ans << endl;
  return 0;
}

3. 数论分块

数论分块又称整除分块，解决下标带有整除值的和式。最基本的和式形如

数论分块的核心结论是 n 的不同整除值的数量级为 \sqrt n。本小节将从该结论出发，介绍数论分块的基本算法以及各种扩展，如向上取整的数论分块，高维数论分块等。数论分块也是高级筛法的前置要求。

3.1 算法介绍

定义（整除值）

首先考虑求和式：

注意求和上指标与取整式的被除数相等。本节最后会讨论不相等的情况。

我们只关心 g 在所有 n 的整除值处的取值。如果整除值的数量不多，且 f 的前缀和可以快速计算，则可以转换贡献形式，将原式写成若干个 g(\lfloor \frac n i\rfloor) 乘以一段 f 的和。

当 i 较大时，\lfloor \frac n i\rfloor 被限制在较小范围内，大部分相同。结合 \min(i, \frac n i) \le \sqrt n，可以想到根号分治。

结论（整除值的数量）

**证明** 当 $i \leq \sqrt n$ 时，因为 $i$ 只有 $\lfloor \sqrt n \rfloor$ 个，所以 $\lfloor \frac n i\rfloor$ 只有不超过 $\lfloor \sqrt n \rfloor$ 个不同的取整。 当 $i > \sqrt n$ 时，因为 $\lfloor \frac n i\rfloor \leq \sqrt n$，所以 $\lfloor \frac n i\rfloor$ 也只有不超过 $\lfloor \sqrt n \rfloor$ 个不同的取值。

根据该结论，枚举 \mathcal{O}(\sqrt n) 种整除值 d，求出最小和最大的 i 使得 \lfloor \frac n i \rfloor = d，分别记为 l, r，则原式可写为

还剩一个问题：如何不重不漏地考虑所有整除值 d，并算出其对应的极长区间 [l, r]？

结论

给定 d，使得 \lfloor \frac n i\rfloor \geq d 的最大的正整数 i 为 \lfloor \frac n d\rfloor。

证明

因为 d 都是正整数，所以 \lfloor \frac n i\rfloor \geq d 当且仅当 \frac n i\geq d，当且仅当 i\leq \frac n d。

因此，给定整除值 d，\lfloor \frac n i\rfloor = d 要求 \lfloor \frac n i\rfloor \geq d 且 \lfloor \frac n i\rfloor < d + 1，即 \lfloor \frac n {d + 1}\rfloor < i \leq \lfloor \frac n d\rfloor。

考虑 从小到大枚举所有极长区间。因为 \lfloor \frac n x\rfloor 随着 x 增大而单调不增，所以相当于 从大到小枚举整除值。第一个整除值是 n，对应 l = r = 1。第二大的整除值对应的 l 为 2，由此算出整除值 \lfloor \frac n 2\rfloor，继而由上述结论算出对应的 r。

一般地，给定整除值 d 和对应的 [l, r]，如果 d\neq 1，那么下一个（比它小的最大的）整除值 d' 对应的区间的左端点 l' 等于 r + 1，从而算出整除值 d' \gets \lfloor \frac n {l'}\rfloor 和对应的 r'\gets \lfloor \frac n {d'}\rfloor = \left \lfloor \frac n {\lfloor n / l'\rfloor}\right\rfloor。注意：区间右端点一定是整除值。

从下图可以看出，随着 x 增大，整除值以及对应区间的变化：当前整除值的下一个整除值是 \lfloor \frac n {r + 1} \rfloor，对应区间的左端点是 r + 1。

>

若 O(1) 计算 g 和 f 的前缀和在单个整除值处的取值，则算法的时间复杂度为 \mathcal{O}(\sqrt n)。

特别地，当求和上指标（记为 m）不等于被除数 n 的时候，和式形如 \sum_{i = 1} ^ m f(i) g(\lfloor \frac n i\rfloor)。

• 为了处理 n > m 的情况，r 应与 m 取较小值。
• 为了处理 n < m 的情况，当 \lfloor \frac n i\rfloor = 0 时，直接令 r\gets m。

结论（整除值的结构）

小于 \sqrt n 的整除值是小于 \sqrt n 的所有正整数，不小于 \sqrt n 的整除值是所有 \lfloor \frac n i\rfloor，其中 i 是不超过 \sqrt n 的正整数。

3.2 扩展问题

数论分块的算法框架简单，有多种变形。

3.2.1 向上取整

将和式中的向下取整改成向上取整。

同样地，\lceil \frac n x\rceil 随着 x 增大而单调不增，所以算法框架不变，依然是从小到大考虑每段区间。只需对左边界 l 求出使得 \lceil\frac n l \rceil = \lceil\frac n r \rceil 的最大的 r。

设 k = \lceil\frac n l\rceil，则要求 \frac n r > k - 1。

第二步的依据是 n, k, r 均为正整数。因此，令 r\gets \lfloor\frac{n - 1}{k - 1}\rfloor 即可。

注意特判 k = 1 的情况，此时 r 需要取实际上界。

3.2.2 高维数论分块

当和式有若干下取整，形如

时，只需稍作修改，令

也就是取所有 n_j 的下一个 “断点” 中最小的那个。

忽略 f 和 g_i 的计算，时间 \mathcal{O}(\sum \sqrt {n_j})。

称存在 n_j 满足 \lfloor \frac {n_j} {i}\rfloor \neq \lfloor \frac {n_j} {i + 1}\rfloor 的 i 为断点，则总断点数量为每个下取整式的断点数量相加（而不是相乘）。在相邻两个断点之间，对每个 n_j，所有 \lfloor \frac {n_j} i\rfloor 都是相等的。

3.2.3 数论分块嵌套

数论分块的嵌套，即对外层数论分块的每个整除值 d，内层还要做规模为 d 的数论分块。常见于计算 g(\lfloor \frac n i \rfloor) 需要数论分块的情况，如第四章例题 P5518 的最后一部分。

写起来和普通数论分块一样，核心在于时间复杂度分析：

• 对小于 \sqrt n 的整除值，贡献为 \int_1 ^ {\sqrt n} \sqrt {x} \mathrm{d} x = \Theta(n ^ {\frac 3 4})。
• 对大于 \sqrt n 的整除值，贡献为 \int_1 ^ {\sqrt n} \sqrt n x ^ {-\frac 1 2} \mathrm{d} x = \Theta(n ^ {\frac 3 4})。

结论（整除值的根号和）

所有整除值的根号和在 n ^ {3 / 4} 级别。

杜教筛的复杂度分析也用到了该结论。

我们还得到了一个有趣的结论：n 的小于 \sqrt n 和大于 \sqrt n 的整除值的根号和是同阶的，虽然后者严格比前者大。算出积分，前者系数为 \frac 2 3，后者系数为 2，差了大约三倍。

3.3 例题

更多例题见第五章莫比乌斯反演。

[模拟赛] 你还没有卸载吗

给定 A_1, B_1, A_2, B_2, N，求有多少 x\in [1, N] 使得 B_1 + \lfloor\frac{A_1}{x}\rfloor = B_2 + \lfloor\frac{A_2}{x}\rfloor。

直接二维数论分块即可。时间 \mathcal{O}(\sqrt V)。

另解

考虑数论分块 [l, r] 固定整除值 \frac{A_1} x 解出 d = \frac{A_2}{x}，反推出 x 的范围 [l, r] \cap [\frac{A_2}{d + 1} + 1, \frac{A_2}{d}]。

#include <bits/stdc++.h>
using namespace std;
int T, a1, b1, a2, b2, n;
int main() {
  cin >> T;
  while(T--) {
    int ans = 0;
    cin >> a1 >> b1 >> a2 >> b2 >> n;
    for(int l = 1, r = 1; l <= n; l = r + 1) {
      r = min(n, min(a1 / l ? a1 / (a1 / l) : n, a2 / l ? a2 / (a2 / l) : n));
      if(b1 + a1 / l == b2 + a2 / l) ans += r - l + 1;
    }
    cout << ans << endl;
  }
  return 0;
}

P2260 [清华集训 2012] 模积和

求 \sum_{i = 1} ^ n n \bmod i 是经典问题：拆成 \sum_{i = 1} ^ n (n - \lfloor\frac n i\rfloor i) 后数论分块，时间复杂度 \mathcal{O}(\sqrt n)。

原式变形为

使用数论分块解决。

你可能需要：

\sum_{i = 1} ^ n i ^ 2 = \frac {n(n + 1)(2n + 1)} 6.

时间 \mathcal{O}(\sqrt n)。代码。

*P3579 [POI2014] PAN-Solar Panels

不错的题目。

当 \lfloor\frac {a - 1} k\rfloor < \lfloor\frac b k\rfloor 且 \lfloor\frac{c - 1} k\rfloor < \lfloor\frac d k\rfloor 时，[a, b] 和 [c, d] 均含有 k 的倍数。答案为所有这样的 k 的最大值。

我们当然可以四维数论分块，但注意到在使得 \lfloor\frac b k \rfloor 相同且 \lfloor \frac d k\rfloor 相同的 k 的区间 [l, r] 当中，选择 k = r 可以使 \lfloor \frac{a - 1} k\rfloor 和 \lfloor \frac {c - 1} k\rfloor 尽可能小，更有机会满足要求。若 k = r 都不满足条件，则 l\leq k \leq r 均不满足条件。因此二维数论分块即可。

时间 \mathcal{O}(T\sqrt V)。代码。

*CF1603C Extreme Extension

数论分块优化 DP。

一个数如何分裂由后面分裂出来的数的最小值决定，所以贪心使分出来的数尽量均匀。例如，若 9 要分裂为若干个比 4 小的数，那么 3, 3, 3 比 2, 3, 4 更优。

从后往前考虑。对每个位置 i 和值 j\in [1, a_i]，求出有多少以位置 i 开头的子段根据上述贪心策略分裂出的最小值为 j（j 由 a_i 分裂零次或若干次得到），记为 f_{i, j}。

考虑 f_{i + 1, j} 往前转移，需要将 a_i 分裂成若干不超过 j 的数，最少需要分裂成 \lceil \frac {a_i} j \rceil 个数。新的最小值是多少？将 a_i 分裂成 c 个数，这些数最小值的最大值为 \lfloor \frac {a_i} c \rfloor。

注意到，对于固定的分裂次数，分裂出的值也是确定的。考虑枚举使得分裂次数相同的区间 [l, r]，即 a_i 整除 [l, r] 内所有数向上取整的结果相同，可以通过向上取整的数论分块实现。

设 c = \lceil \frac {a_i} l \rceil 表示分裂出的数的个数，则分裂出的数的最小值为 v = \lfloor \frac {a_i} c \rfloor。\sum_{j = l} ^ r f_{i + 1, j} 转移到 f_{i, v}。

考虑在每个位置处统计该位置在所有子段中的总分裂次数之和，则贡献为 i\times (c - 1) \times f_{i , v}。其含义为，共有 f_{i, v} 个以 i 开头的子段使得 a_i 要分裂出 c 个数，即分裂 c - 1 次。同时，若子段 [i, k] 在 i 处分裂 c - 1 次，则对于任意子段 [x, k] 满足 1\leq x\leq i，a_i 分裂的次数都是 c - 1，因为 a_i 的分裂不受前面的数的影响。

注意，当 c = 1 时，f_{i, v} 即 f_{i, a_i} 需要加 1，表示新增以 a_i 结尾的子段。

用 vector 存储所有 f_i 并转移，时间 \mathcal{O}(n\sqrt {a_i})。滚动数组优化后空间 \mathcal{O}(n)。代码。

4. 欧拉函数

欧拉函数是非常重要的数论函数。

4.1 定义与性质

另一种证明

设与 n 互质的数为 a_{1\sim \varphi(n)}，那么在 [0, nm - 1] 内与 n 互质的数为 jn + a_i，其中 1\leq i \leq \varphi(n)，0\leq j < m。

因为 n\perp m，所以 jn 在模 m 下互不相同，否则 (j - j')n 是 m 的倍数，可知 j\equiv j'\pmod m，矛盾。

因此，对每个 a_i，(jn + a_i)\bmod m 取遍 0\sim m - 1，其中有 \varphi(m) 个和 m 互质。

在 [0, nm - 1] 内共有 \varphi(n)\varphi(m) 个数同时和 n, m 互质（于是和 nm 互质）。\square

因为 \varphi 是积性函数，所以只需考虑其在质数幂处的取值。

性质 2

设 p 是质数，则 \varphi(p ^ k) = (p - 1)p ^ {k - 1}。

证明

因为 p 是质数，所以和 p 不互质当且仅当是 p 的倍数，共有 p ^ {k - 1} 个。\square

根据性质 2 可线性筛欧拉函数。写成 \varphi(p) = p - 1，\varphi(p ^ k) = p\varphi(p ^ {k - 1})\ (k\geq 2)，方便线性筛。

int cnt, pr[N], phi[N], vis[N];
void sieve() {
    phi[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!vis[i]) pr[++cnt] = i, phi[i] = i - 1;
        for(int j = 1; j <= cnt && i * pr[j] < N; j++) {
            vis[i * pr[j]] = 1;
      phi[i * pr[j]] = (pr[j] - 1) * phi[i];
            if(i % pr[j] == 0) {
        phi[i * pr[j]] = pr[j] * phi[i];
        break;
     }
        }
    }
}

性质 1 和性质 2 给出了直接计算欧拉函数的公式。

性质 3（计算欧拉函数）

设 n 的唯一分解为 \prod_{i = 1} ^ m p_i ^ {c_i}，则

\varphi(n) = n\times \prod_{i = 1} ^ {m} \frac {p_i - 1} {p_i}.

int phi(int x) {
  int ans = x;
  for(int i = 2; i * i <= x; i++)
    if(x % i == 0) {
      while(x % i == 0) x /= i;
      ans = ans / i * (i - 1);
    }
  return ans / x * max(1, x - 1);
}

计算 \varphi(n) 的时间是分解质因数的 \mathcal{O}(\sqrt n)，使用 Pollard-Rho 算法可以做到 \mathcal{O}(n ^ {1 / 4})。

欧拉函数的计算式也可以通过容斥原理证明。

证明

根据容斥原理，去掉所有被至少一个 n 的质因数整除的数，加上至少被两个 n 的质因数整除的数，以此类推，最终得到

\varphi(n) = n \sum_{T\subseteq S} \frac {(-1) ^ {|T|}}{\prod_{p\in S} p}

其中 S 是 n 的质因数集合。上式是 n \prod_{i = 1} ^ m (1 - \frac 1 {p_i}) 的直接展开。\square

根据上式推出性质 1 和性质 2 是平凡的。

接下来给出一些常用的欧拉函数的性质。

性质 4

若 n\mid m，则 \varphi(nm) = n\varphi(m)。

证明

• 直观理解：因为 nm 相较 m 没有增加质因数，所以原来与 m 互质的数仍与 nm 互质。[0, nm - 1] 当中与 m 互质的数的个数为 n\varphi(m)，因为一个与 m 互质的数加上 m 的倍数后仍然与 m 互质。

容易发现 n\mid m 的条件可弱化为 m 含有 n 的所有质因数。在考虑互质的时候，质因数的幂次是不重要的，只有质因数集合是重要的。

性质 5

对 n \geq 3，2\mid \varphi(n)。

证明

若 x \perp n，则 n - x\perp n。所有小于 n 且与 n 互质的数能一一配对。

x = n - x$ 是特例，此时 $x = \frac n 2$，$\gcd(x, n) = x \neq 1$。$\square

也可以考虑计算式。对于如果只含质因数 2，则 \varphi(n) = \frac n 2 是偶数。否则奇质因数 p 的 \frac {p - 1} {p} 将导致 \varphi(n) 是偶数。

性质 6

若 n \mid m，则 \varphi(n) \mid \varphi(m)。

回忆同余理论一开始的基本知识：

性质 7

对 d\mid n，使得 \gcd(n, x) = d 的 x\in [0, n - 1] 的数量为 \varphi(\frac n d)。

证明

\gcd(n, x) = d$ 要求 $x$ 是 $d$ 的倍数且 $\gcd(\frac n d, \frac x d) = 1$。因为 $\frac x d$ 的范围是 $[0, \frac n d - 1]$，所以 $x$ 的数量为 $\varphi(\frac n d)$。$\square

考虑到 0\sim n - 1 的每个数和 n 的最大公约数都是 n 的因数，得到欧拉反演公式。

性质 8（Euler 反演）

\sum_{d\mid n}\varphi(d) = n.

证明

枚举每个数和 n 的最大公约数 d，由性质 7，

n = \sum_{d\mid n} \sum_{i = 0} ^ {n - 1} [\gcd(n, i) = d] = \sum_{d\mid n} \varphi\left(\frac n d\right) = \sum_{d\mid n} \varphi(d). \square