标签：lfloor 完工 limits dfrac sum 莫反 杜教 mu rfloor

\(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)\)。
• \(*\)，狄利克雷卷积：\((f * g)(x) = \sum\limits_{d|n}f(d)g(\dfrac n d)\)。
  • 这运算看起来很奇怪。后文会详细说明这种运算的性质。

常见的数论函数

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

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

狄利克雷卷积

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

\[h(n) = \sum\limits_{d|n}f(d)g(\dfrac n d) \]

则

\[h = f * g \]

狄利克雷卷积的性质

• 交换律。
• 结合律。
• 有单位元 \(\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)\)。
• 重要：两个积性函数的狄利克雷卷积依然是积性函数。
• 重要：积性函数的狄利克雷逆元依然是积性函数。

证明留作练习

\(1\) 的逆元：莫比乌斯函数

不妨起个名字叫 \(\mu\)。

\(1\) 是积性函数，所以 \(\mu\) 也是积性函数。

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

\((\mu \cdot \mu)^{-1}\) 也有个名字，叫作刘维尔函数 \(\lambda\)。

常见的狄利克雷卷积

• \(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\)。

\[\begin{aligned} & \sum\limits_{i=1}^n \sum\limits_{j=1}^m [\gcd(i,j)=1] \\ =& \sum\limits_{i=1}^n \sum\limits_{j=1}^m \sum\limits_{d|\gcd(i,j)} \mu(d) \\ =& \sum\limits_{i=1}^n \sum\limits_{j=1}^m \sum\limits_{d=1}^n [d|i][d|j] \mu(d) \\ =& \sum\limits_{d=1}^n \mu(d) \sum\limits_{i=1}^n \sum\limits_{j=1}^m [d|i][d|j] \\ =& \sum\limits_{d=1}^n \mu(d) \left\lfloor\dfrac nd \right\rfloor \left\lfloor\dfrac md \right\rfloor \end{aligned} \]

线性筛 \(\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\)。

\[\begin{aligned} & \sum\limits_{i=1}^n \sum\limits_{j=1}^m \gcd(i,j) \\ =& \sum\limits_{d=1}^n d \sum\limits_{i=1}^n \sum\limits_{j=1}^m [\gcd(i,j) = d] \\ =& \sum\limits_{d=1}^n d \sum\limits_{i=1}^{\lfloor \frac n d \rfloor} \sum\limits_{j=1}^{\lfloor \frac m d \rfloor} [\gcd(i,j) = 1] \\ =& \sum\limits_{d=1}^n d \sum\limits_{i=1}^{\lfloor \frac n d \rfloor} \sum\limits_{j=1}^{\lfloor \frac m d \rfloor} \sum\limits_{t=1}^n [t|i][t|j] \mu(t) \\ =& \sum\limits_{d=1}^n d \sum\limits_{t=1}^n \mu(t) \sum\limits_{i=1}^{\lfloor \frac n d \rfloor} \sum\limits_{j=1}^{\lfloor \frac m d \rfloor} [t|i][t|j] \\ =& \sum\limits_{d=1}^n d \sum\limits_{t=1}^n \mu(t) \left\lfloor \dfrac n {dt} \right\rfloor \left\lfloor \dfrac m {dt} \right\rfloor \\ =& \sum\limits_{T=1}^n \left\lfloor \dfrac n T \right\rfloor \left\lfloor \dfrac m T \right\rfloor \sum\limits_{d|T} d \mu(\dfrac T d) \\ =& \sum\limits_{T=1}^n \varphi(T) \left\lfloor \dfrac n T \right\rfloor \left\lfloor \dfrac m T \right\rfloor \\ \end{aligned} \]

解释：

• 把 \(dt\) 用 \(T\) 代替了。
• \(\sum\limits_{d|T} d \mu(\dfrac T d) = \varphi(T)\)。（\(\text{Id} * \mu = \varphi\)）

线性筛 \(\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。

\[\begin{aligned} & \sum\limits_{i=1}^n \sum\limits_{j=1}^m A_i B_j C_{\gcd(i,j)} \\ =& \sum\limits_{d=1}^n C_d \sum\limits_{i=1}^n \sum\limits_{j=1}^m A_i B_j [\gcd(i,j) = d] \\ =& \sum\limits_{d=1}^n C_d \sum\limits_{i=1}^{\lfloor \frac n d \rfloor} \sum\limits_{j=1}^{\lfloor \frac m d \rfloor} A_{id} B_{jd} [\gcd(i,j) = 1] \\ =& \sum\limits_{d=1}^n C_d \sum\limits_{i=1}^{\lfloor \frac n d \rfloor} \sum\limits_{j=1}^{\lfloor \frac m d \rfloor} A_{id} B_{jd} \sum\limits_{t=1}^n [t|i][t|j] \mu(t) \\ =& \sum\limits_{d=1}^n C_d \sum\limits_{t=1}^n \mu(t) \sum\limits_{i=1}^{\lfloor \frac n d \rfloor} \sum\limits_{j=1}^{\lfloor \frac m d \rfloor} A_{id} B_{jd} [t|i][t|j] \\ =& \sum\limits_{d=1}^n C_d \sum\limits_{t=1}^n \mu(t) \sum\limits_{i=1}^{\lfloor \frac n {dt} \rfloor} \sum\limits_{j=1}^{\lfloor \frac m {dt} \rfloor} A_{idt} B_{jdt} \\ =& \sum\limits_{T=1}^n \left(\sum\limits_{i=1}^{\lfloor \frac n T \rfloor} A_{iT}\right) \left(\sum\limits_{j=1}^{\lfloor \frac m T \rfloor} B_{jT}\right) \left(\sum\limits_{d|T} C_d \mu(\dfrac T d)\right) \\ =& \sum\limits_{T=1}^n \left(\sum\limits_{i=1}^{\lfloor \frac n T \rfloor} A_{iT}\right) \left(\sum\limits_{j=1}^{\lfloor \frac m T \rfloor} B_{jT}\right) (C * \mu)(T) \\ \end{aligned} \]

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

狄利克雷后缀和 + 狄利克雷差分可以做到 \(O(n \log \log n)\)。

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

例 3.5：狄利克雷四变换

// TODO: 四变换

例 4：乘积与数论函数

[SDOI2015] 约数个数和

// TODO: 函数乘积

例 5：积性函数求和

// TODO: ZAK

杜教筛

定义 \(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})\) 之内求出。

\[\begin{aligned} & \sum\limits_{i=1}^n (f * g)(i) \\ =& \sum\limits_{i=1}^n \sum\limits_{xy=i} f(x) g(y) \\ =& \sum\limits_{y=1}^n g(y) \sum\limits_{xy \le n} \\ =& \sum\limits_{y=1}^n g(y) S_f\left(\left\lfloor \dfrac n y \right\rfloor\right) \end{aligned} \]

所以：

\[S_f(n) = \dfrac 1 {g(1)} \left(S_{f*g}(n) - \sum\limits_{i=2}^n g(i) S_f\left(\left\lfloor \dfrac n i \right\rfloor\right)\right) \]

数论分块 + 记忆化。（有定理：\(\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 可得：

\[\begin{aligned} & \sum\limits_{i=1}^n \sum\limits_{j=1}^n ij\gcd(i,j) \\ =& \sum\limits_{T=1}^n \varphi(T)T^2 \times S_{\text{Id}}(\lfloor \dfrac n T \rfloor)^2 \end{aligned}\]

问题转化为求出 \(\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})\)。
• 有时 \(g\) 或 \(f * g\) 的基本和组较难计算。但是 \(f = g * h\) 这样构造出来的 \(g\) 和 \(h\) 的基本和组好算。
  • \(\sigma_k * \mu = \text{Id}_k\)。\(\mu\) 的基本和组需要一次杜教筛，麻烦。
  • 但是 \(\sigma_k = \text{Id}_k * 1\)。基本和组简单。
  • 从下文的柿子能看出，这种方法比杜教筛更加自由，只求一个前缀和的时候甚至不需要求出基本和组。
  • 推柿子：

\[\begin{aligned} & \sum\limits_{i=1}^n \sum\limits_{d|i} g(d)h(\dfrac i d) \\ =& \sum\limits_{d=1}^n g(d) \sum\limits_{i=1}^{\lfloor \frac n d \rfloor} h(i) \\ =& \sum\limits_{d=1}^n g(d) S_h\left(\left\lfloor \dfrac n d \right\rfloor\right) \end{aligned}\]

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

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

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

\[f_p(x) = \sum\limits_{i=0}^\infty f(p_i) x_i \]

对于两个积性函数 \(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\)
• \(\lambda\)：\(\dfrac 1 {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\)）显然是积性函数，考虑其贝尔级数：

\[f_p(x) = \dfrac {1+x} {(1-x)^2} \]

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

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

还有吗……？

OI 中会遇到的数论题目基本到此为止了。还有一些毒瘤 [SDOI2018] 旧试题

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

就这样罢。

标签：lfloor,完工,limits,dfrac,sum,莫反,杜教,mu,rfloor
From： https://www.cnblogs.com/AugustLight/p/18062896