本文中 $p$ 是质数。$p^k$ 是质数的幂。

广告

https://github.com/August-Light/NTFuncs

这是一个关于各种数论函数的 Python 库！

前置知识

• 数论分块
  • 模板题 1：[UVA11526] H(n)
  • 模板题 2：[Luogu P2261] [CQOI2007] 余数求和
• 线性筛 & 线性筛数论函数
  • 模板题 1：[Luogu P3383] 【模板】线性筛素数
  • 模板题 2：[Luogu P2158] [SDOI2008] 仪仗队

数论函数

数论函数：定义域为正整数的函数。

• 对于数论函数 $f$，对于任意 $\gcd(n,m) = 1$，如果有 $f(nm) = f(n)f(m)$，则 $f$ 为积性函数。
  • 积性是十分美好的性质。对于积性函数，你只需要考虑 $p^k$ 处的取值，对于其它数只需要分解质因数然后乘起来就好了。
• 对于数论函数 $f$，对于任意 $n,m$，如果有 $f(nm) = f(n)f(m)$，则 $f$ 为完全积性函数。

数论函数的运算

• $+$，加法：$(f + g)(x) = f(x) + g(x)$。
• $-$，减法：$(f - g)(x) = f(x) - g(x)$。
• $\cdot$，点积：$(f \cdot g)(x) = f(x) \times g(x)$。

• $*$，Dirichlet 卷积：$(f * g)(x) = \sum\limits_{d

  n}f(d)g(\dfrac n d)$。

  • 这运算看起来很奇怪。后文会详细说明这种运算的性质。

常见的数论函数

这一部分的记号好像每个人都不太一样？

• $\varepsilon(x) = [x = 1]$。【完全积性函数】
• $\text{Id}_k(x) = x^k$。【完全积性函数】
  • 特殊地，$\text{Id}_0$ 可以记为 $1$。
  • 特殊地，$\text{Id}_1$ 可以记为 $\text{Id}$。
• $\varphi(x)$ 为欧拉函数（A000010）。【积性函数】
  • $\varphi(x)$ 为 $[1,x]$ 中与 $x$ 互质的数的个数。
• $\sigma_k(x) = \sum\limits_{d \mid x} x^k$。【积性函数】
  • 特殊地，$\sigma_0$ 可以记为 $d$。（也记作 $\tau$，较少见）
  • 特殊地，$\sigma_1$ 可以记为 $\sigma$。
• $\mu(x)$ 为莫比乌斯函数（A008683）。【积性函数】
  • 后文会详细说明。

Dirichlet 卷积

如果一个数论函数 $h$ 与数论函数 $f,g$ 有以下关系：

则

Dirichlet 卷积的性质

• 交换律。
• 结合律。
• 有单位元 $\varepsilon$。
• 每个数论函数 $f$（除了 $f(1) = 0$ 的）都有逆元（即 $f * g = \varepsilon$）：

  • $g(n) = \dfrac 1 {f(1)} \left([n = 1] - \sum\limits_{i

    n, i \ne 1} f(i)g\left(\dfrac n i \right)\right)$

  • $f$ 的逆元记作 $f^{-1}$。
• 与加法的分配律：$(f + g) * h = f * h + g * h$。
• 与点积的分配律（$h$ 为完全积性函数）：$(f * g) \cdot h = (f \cdot h) * (g \cdot h)$。
• 重要：两个积性函数的 Dirichlet 卷积依然是积性函数。
• 重要：积性函数的 Dirichlet 逆元依然是积性函数。

证明留作练习

$1$ 的逆元：莫比乌斯函数 $\mu$

$1$ 是积性函数，所以它的逆 $\mu$ 也是积性函数。

根据定义，不难推导得到 $\mu(p^k) = \begin{cases} 1 & k=0 \ -1 & k=1 \ 0 & k>1 \end{cases}$。

常见的 Dirichlet 卷积

• $1 * \mu = \varepsilon$。
• $\varphi * 1 = \text{Id}$ 即 $\text{Id} * \mu = \varphi$。
  • 证明留做习题。
  • 这一条非常重要。
• $1 * 1 = d$ 即 $d * \mu = 1$。
• $\text{Id}_k * 1 = \sigma_k$ 即 $\sigma_k * \mu = \text{Id}_k$。
• $\lambda * (\mu \cdot \mu) = \varepsilon$。

莫比乌斯反演

例 1：最简单的莫比乌斯反演

[POI2007] ZAP-Queries：求 $\sum\limits_{i=1}^n \sum\limits_{j=1}^m [\gcd(i,j)=1]$。要求 $O(n)$。（挑战：$O(n^{\frac 2 3})$）

推导：不妨设 $n \le m$。

线性筛 $\mu$ 时间复杂度 $O(n)$。

杜教筛 $\mu$ 时间复杂度 $O(n^{\frac 2 3})$。

例 2：难一点的莫比乌斯反演

[Luogu P2398] GCD SUM：求 $\sum\limits_{i=1}^n \sum\limits_{j=1}^m \gcd(i,j)$。要求 $O(n)$。（挑战：$O(n^{\frac 2 3})$）

推导：不妨设 $n \le m$。

线性筛 $\varphi$ 时间复杂度 $O(n)$。

杜教筛 $\varphi$ 时间复杂度 $O(n^{\frac 2 3})$。

例 3：例 2 的一般化

给定 $A,B,C$，求 $\sum\limits_{i=1}^n \sum\limits_{j=1}^m A_i \times B_j \times C_{\gcd(i,j)}$。要求 $O(n \log n)$。（挑战：$O(n \log \log n)$）

推导：膜拜 ZAK。

直接做是调和级数的 $O(n \log n)$。

Dirichlet 后缀和 + Dirichlet 差分可以做到 $O(n \log \log n)$。

• 练习：[Luogu P6810]「MCOI-02」Convex Hull 凸包

例 3.5：Dirichlet 四变换

先看代码：

// primes 为一个 vector，需要线性筛预处理
for (auto j : primes)
    for (int i = 1; i * j <= n; i++)
        f[i * j] += f[i];

理解 1：高维空间

每一个数可以看成一个高维空间中的点。具体来说，$n = \prod p_i^{k_i}$，则 $n$ 就对应 $(k_1, k_2, k_3, \cdots)$ 这个点。

经过上述转化，那么本题就变为了高维前缀和问题。普通高维前缀和有显而易见的 $O(3^n)$ 优化到 $O(n2^n)$ 的做法，此题也一样，朴素的 $O(n \log n)$ 可以被优化到 $O(n \log \log n)$。

这个理解可以很容易拓展到 Dirichlet 四变换：

• Dirichlet 前缀和（高维前缀和）

  • $g_i = \sum\limits_{d

    i} f_d$

• Dirichlet 前缀差分（前一个的逆运算）
• Dirichlet 后缀和（高维后缀和）

  • $g_i = \sum\limits_{i

    d} f_d$

• Dirichlet 后缀差分（前一个的逆运算）

理解 2：拆开积性函数

显而易见的，$g = f * 1$。

定义 $F_p(x) = \begin{cases} F(x) & x=p^k \ 0 & \text{otherwise} \end{cases}$。（此题 $F = 1$）

不难发现，$F = F_{p_1} * F_{p_2} * \cdots$（$p_i$ 为第 $i$ 个质数）。

而把一个函数卷上 $F_p$ 是简单的，只需要 $O\left(\dfrac n p\right)$ 时间。总复杂度 $O(n \log \log n)$。

推广：Dirichlet 前缀差分即为 $g = f * \mu$，可以用一样的方法。事实上，卷任何积性函数都可以。

例 4：乘积与数论函数

[SDOI2015] 约数个数和：求 $\sum\limits_{i=1}^n \sum\limits_{j=1}^m d(ij)$。要求 $O(n) - O(\sqrt n)$。

有以下四个常见的函数乘积结论：

• $\mu(ij) = [i \perp j] \mu(i) \mu(j)$

• $d(ij) = \sum\limits_{x

  i} \sum\limits_{y

  j} [x \perp y]$

• $\varphi(ij) = \dfrac {\varphi(i) \varphi(j) \gcd(i,j)} {\gcd(\varphi(i,j))}$

• $\sigma_k(ij) = \sum\limits_{x

  i} \sum\limits_{y

  j} [x \perp y] (\dfrac {xj} y)^k$

（如何发现这些结论呢？注意到这些都是积性函数，所以只考虑 $p^k$，即令 $i=p^a, j=p^b$，然后瞎推式子）

在知道了结论之后，推导式子也就不难了，留作练习。

• 练习：[Luogu P4240] 毒瘤之神的考验

例 5：积性函数乘积求和

给定积性函数 $S$，求 $\sum\limits_{i=1}^n \sum\limits_{j=1}^m S(i \times j)$。要求 $O(n \log n \log \log n)$。

膜拜 ZAK。

枚举 $g = \gcd(i,j)$。推导：

引理：对于积性函数 $S$ 与自然数 $c$，对于任意 $i \perp j$，有：

证明：只考虑质数幂处，$i,j$ 互质，必有一个为 $1$，显然左右两侧相等。

构造一个函数 $H_g(x) = \dfrac {S(g^2 x)} {S(g^2)}$，根据上文引理可得 $H_g$ 是积性函数。

继续推导：

套进例 3 式子（$A = H_g$，$B = H_g$，$C = \varepsilon$）。

时间复杂度 $O(\sum\limits_{g=1}^n \dfrac n g \log \log \dfrac n g) = O(n \log n \log \log n)$。

• 练习：[Luogu P8570] [JRKSJ R6] 牵连的世界

杜教筛

定义 $S_f(n) = \sum\limits_{i=1}^n f(i)$。

基本和组（也叫块筛）：对于数论函数 $f$ 与正整数 $n$，$S_f\left(\left\lfloor \dfrac n i \right\rfloor\right)$ 的一系列值被称为基本和组。

• 就是数论分块时会用到的那些值。
• 显然 $S_f\left(\left\lfloor \dfrac n i \right\rfloor\right)$ 的不同值只有 $O(\sqrt n)$ 个。

杜教筛用于在低于线性的时间内求一个函数的前缀和的基本和组。

前提条件：对于要求基本和组的函数 $f$，能够构造一个函数 $g$，使得 $g$ 与 $f * g$ 的基本和组都能在 $O(n^{\frac 2 3})$ 之内求出。

（事实上，根据这个式子，可以在 $O(n^{\frac 2 3})$ 时间内根据 $f,g$ 的基本和组求出 $f * g$ 的基本和组，与杜教筛相反）

所以：

数论分块 + 记忆化。（有定理：$\left\lfloor \dfrac {\left\lfloor \dfrac a b \right\rfloor} c \right\rfloor = \left\lfloor \dfrac a {bc} \right\rfloor$，所以确实会求出整个基本和组）

用微积分知识可得时间复杂度为 $O(n^{\frac 3 4})$。

预先线性筛处理 $S_f$ 在前 $O(n^{\frac 2 3})$ 的值，其他值用上文办法处理，可以用微积分知识证明时间复杂度 $O(n^{\frac 2 3})$。

关于记忆化：

• 用 unordered_map 最简单，并且多测的话还能重复利用，有助于卡常。
• 也可以以 $\lfloor \dfrac n x \rfloor$ 作为标识存储 $S_f(x)$ 的值。不会出现重复。但是多测要记得清空。
  • https://www.luogu.com/article/hjw4837h

杜教筛例题

例 1：模板

[Luogu P4213]【模板】杜教筛：求 $S_\varphi(n)$ 与 $S_\mu(n)$。要求 $O(n^{\frac 2 3})$。

• $\varphi$：$\varphi * 1 = \text{Id}$
• $\mu$：$\mu * 1 = \varepsilon$

直接杜教筛即可。

例 2：莫比乌斯反演 + 杜教筛

[Luogu P3768] 简单的数学题：求 $\sum\limits_{i=1}^n \sum\limits_{j=1}^n ij\gcd(i,j)$。模数为大质数。要求 $O(n^{\frac 2 3})$。

由莫反例 3 可得：

问题转化为求出 $\varphi \cdot \text{Id}_2$ 的基本和组。

《注意到》有 $(\varphi \cdot \text{Id}_2) * \text{Id}_2 = \text{Id}_3$。

杜教筛即可。

杜教筛嵌套

• 常数次杜教筛嵌套，复杂度保持 $O(n^{\frac 2 3})$。
  • 假设你用 $d * \mu = 1$ 来计算 $d$ 的前缀和。
  • 首先用 $O(n^{\frac 2 3})$ 算出 $\mu$ 的基本和组。
  • 然后用 $O(n^{\frac 2 3})$ 算出 $d$ 的基本和组。
  • 总复杂度还是 $O(n^{\frac 2 3})$。

例 3：贝尔级数：系统地为积性函数构造杜教筛

[SP20173] DIVCNT2 - Counting Divisors (square)：求 $\sum\limits_{i=1}^n d(i^2)$。要求 $O(n^{\frac 2 3})$。

定义一个积性函数 $f$ 的贝尔级数为一个形式幂级数：

对于两个积性函数 $f,g$，$f*g$ 的贝尔级数等于 $f$ 与 $g$ 的贝尔级数相乘。

常见数论函数的贝尔级数：

• $\varepsilon$：$1$
• $\text{Id}_k$：$\dfrac 1 {1 - p^k x}$
  • $1$：$\dfrac 1 {1 - x}$
• $\mu$：$1-x$
• $(\mu \cdot \mu)$：$1+x$
• $\sigma_k$：$\dfrac 1 {(1-x)(1 - p^k x)}$
  • $d$：$\dfrac 1 {(1-x)^2}$
• $\varphi$：$\dfrac {1-x} {1-px}$

本题的函数（$d \circ \text{Id}_2$）显然是积性函数，考虑其贝尔级数：

不难发现：$f = (\mu \cdot \mu) * d$。

Trick：$(\mu \cdot \mu)$ 的前缀和能快速求。[Luogu P4318] 完全平方数

还有吗……？

OI 中会遇到的数论题目基本到此为止了。但是不排除一些毒瘤 [SDOI2018] 旧试题

再往后洲阁筛、Min_25 筛之类的东西我个人认为没有赛场上的实用价值。

就这样罢。