一些杜教筛的构造方法

贝尔级数和狄利克雷生成函数都是构造杜教筛的有力工具，熟练地运用它们可以方便地完成杜教筛的构造。

在阅读本文前，请确保自己已经掌握了杜教筛的基本原理。

贝尔级数

定义

定义数论函数 f(x) 在质数 p 意义下的贝尔级数为

f_p(x)=\sum_{i=0}^{\infty}f(p^i)x^i

这可以看作是数列 \{f(p^0),f(p^1),f(p^2),\cdots\} 的普通生成函数。

一些定理

定理一： 若 f(x) 为完全积性函数，则 f_p(x)=\dfrac{1}{1-f(p)x}。

证明：

\begin{aligned} f_p(x)&=\sum_{i=0}^\infty f(p^i)x^i\\ &=\sum_{i=0}^\infty f(p)^ix^i\\ &=\frac{1}{1-f(p)x} \end{aligned} \square

定理二： f_p\times g_p = (f*g)_p

证明：

\begin{aligned} (f*g)_p&=\sum_{i=0}^\infty (f*g)(p^i)x^i\\ &=\sum_{i=0}^\infty\sum_{j+k=i}f(p^j)g(p^k)x^i\\ &=\sum_{j=0}f(p^j)\sum_{i-k=j,k\ge 0}g(p^k)x^i\\ &=\sum_{j=0}^\infty f(p^j)\sum_{i=j}^\infty g(p^{i-j})x^i\\ &=\sum_{j=0}^\infty f(p^j)\sum_{i=0}^\infty g(p^i)x^{i+j}\\ &=f_p\times g_p \end{aligned} \square

定理三： f_p(x)=g_p(x)\iff f(x)=g(x)

证明：

必要性显然，现证明其充分性。

\begin{aligned} \forall x=\prod p_i^{a_i},f(x)=\prod f(p_i^{a_i})=\prod f_{p_i}(x)[a_i]=\prod g_{p_i}(x)[a_i]=g(x) \end{aligned} \square

这也是用贝尔级数构造杜教筛的基础。

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

\varepsilon_p(x)=1\\ 1_p(x)=\sum_{i=0}^\infty x^i=\frac{1}{1-x}\\ ({\operatorname{id_k}})_p(x)=\sum_{i=0}^\infty p^{ik}x^i=\frac{1}{1-p^kx}\\ \mu_p(x)=1_p(x)^{-1}=1-x\\ \mu^2_p(x)=1+x d_p(x)=\sum_{i=0}^\infty ix^i = \frac{1}{(1-x)^2} (\sigma_k)_p(x)=\sum_{i=0}^\infty x^i\sum_{j=0}^ip^{jk}=\frac{1}{(1-x)(1-p^kx)} \varphi_p(x)=1+\sum_{i=1}^\infty p^{i-1}(p-1)x^i=\frac{1-x}{1-px}

数论函数的点积也会对贝尔级数造成影响。一般地，f(x) 点积 \varepsilon(x) 会变成 \varepsilon_p(x)，点积 1(x) 则不变，点积 \operatorname{id_k} 会使 x 变成 p^kx。例如：

(\mu\cdot\operatorname{id_k})_p(x) = 1-p^kx\\ (\varphi\cdot\operatorname{id_k})_p(x)=\frac{1-p^kx}{1-p^{k+1}x}

一些题目

1. 求函数 f(p^k)=p^k+\lbrack k>0\rbrack(-1)^k 的前缀和。

我们写出 f(x) 的贝尔级数为：

f_p(x) = 1+\sum_{i=1}^\infty (p^i+(-1)^i)x^i=\frac{1}{1-px}+\frac{1}{1+x}-1

考虑构造数论函数 g(x)，使得 g_p(x)=(1-px)(1+x)。此时 h_p(x)=(f*g)_p(x)=f_p(x)\times g_p(x)=1+px^2

观察到 \mu_p(x)=1-x, (\mu\cdot\operatorname{id})_p(x)=(1-px)，则 g_p(x)=(\mu^2\cdot\operatorname{id})_p(x)，由定理三可知 g(x)=\mu^2\cdot\operatorname{id}。

可得 h(n) 非 0 当且仅当 n 所有素因子次数均为 2。S_{h(n)}=\sum\limits_{d-1}^{\sqrt{n}}i\mu^2(i)。这是很易求的。

2. Sum of (-1)^f(n)

求函数 \lambda(n)=(-1)^{f(i)} 的前缀和。其中 f(n) 为 n 质因数分解后各质因子的次数和。

考虑求 \lambda(n) 的贝尔级数。

\begin{aligned} \lambda_p(n)&=\sum_{i=0}^\infty\lambda(p^i)x^i\\ &=\sum_{i=0}^\infty(-1)^ix^i\\ &=\frac{1}{1+x} \end{aligned}

考虑构造 g_p(x)=1+x，此时 \lambda_p(x)\times g_p(x)=1。显然 g_p(x)=\mu_p^2(x)，由定理三可知 g(x)=\mu^2(x)。而 (\lambda*g)_p(x)=\lambda_p(x)\times g_p(x)=1=\varepsilon_p(x)，有 \lambda*g=\varepsilon。而 \mu^2(x) 的前缀和是易求的（具体可以参考 P4318 完全平方数），可以据此进行杜教筛求解。时间复杂度 O(n^{\frac{2}{3}})。

3. 定义数论函数 f(x) = \mu^2 * (\operatorname{id}\times \mu)，求 \sum\limits_{i=1}^nf(i)。

我们写出 f(x) 的贝尔级数 f_p(x)。

\begin{aligned} f_p(x)&=(\mu^2 * (\operatorname{id}\times \mu))_p\\ &=\mu^2_p\times (\operatorname{id}\times \mu)_p\\ &=(1+x)(1-px) \end{aligned}

发现 f_p(x)\times \operatorname{id}_p(x)=1+x=\mu^2_p(x)，由定理二可知 f_p(x)\times \operatorname{id}_p(x)=(f * \operatorname{id})_p，由定理三可知 f * \operatorname{id}=\mu^2，于是即可用杜教筛求解。

狄利克雷生成函数

定义

对于一个数论函数 f，定义其 DGF（狄利克雷生成函数）为：

\tilde{f}(x) = \sum_{i = 1}^{\infty}\frac{f(i)}{i^x}

简单数论函数的 DGF

\begin{aligned} \tilde{\varepsilon}(x) &= 1 \\ \tilde{1}(x) &= \sum_{i = 1}^{\infty}\frac{1}{i^x} = \zeta(x)\\ \tilde{\operatorname{id}_ k}(x) &= \sum_{i = 1}^{\infty}\frac{i^k}{i^x}= \zeta(x-k) \end{aligned}

欧拉乘积公式

对于积性函数 f，有：

\tilde{f}(x) = \prod_{i = 1}^{\infty}\sum_{a=0}^{\infty}\frac{f(p_i^a)}{p_i^{ax}}

证明：

先写出前几项：

\begin{aligned} \prod_{i = 1}^{\infty}\sum_{a=0}^{\infty}\frac{f(p_i^a)}{p_i^x} &= \prod_{i = 1}^{\infty}\left(1+\frac{f(p_i)}{p_i^x}+\frac{f(p_i^2)}{p_i^{2x}} + \cdots\right)\\ &=\left(1+\frac{f(2)}{2^x}+\frac{f(4)}{4^x} + \cdots\right)\left(1+\frac{f(3)}{3^x}+\frac{f(9)}{9^{x}} + \cdots\right)\cdots\\ &= 1 + \frac{f(2)}{2^x} + \frac{f(3)}{3^x} + \frac{f(4)}{4^x} + \frac{f(5)}{5^x} + \frac{f(6)}{6^x} + \cdots \end{aligned}

考虑唯一分解定理，对于任意的正整数 n = \prod_{i=1}^m p_i^{c_i}，对应的就是在 p_i 的幂次中选择第 c_i+1 项，显然这个式子展开后会取到每一个正整数，并且只会出现一次。

那么我们可以根据这个公式写出一些较为复杂的函数的 DGF。

我们重新推导 \tilde{1}，得到 \zeta(x) 的新式子。

\tilde{1}(x) = \prod_{i = 1}^{\infty}\sum_{a=0}^{\infty}\frac{1}{p_i^{ax}} = \prod_{i = 1}^{\infty}\frac{p_i^x}{p_i^x - 1} = \prod_{p}\frac{1}{1 - p^{-x}} = \zeta(x)

因为 \varphi(p^0) = 1,\varphi(p^a) = p^a - p^{a - 1}，那么

\tilde{\varphi}(x) = \prod_{i = 1}^{\infty}\left(1 + (1 - \frac{1}{p_i})\sum_{a=1}^{\infty} \frac{p_i^a}{p_i^{ax}}\right)=\prod_{i = 1}^{\infty}\frac{p_i^x - 1}{p_i^x - p_i} = \frac{\zeta(x - 1)}{\zeta(x)}

因为 \mu(p^0) = 1,\mu(p^1) = -1,\mu(p^a) = 0(a \ge 2)，那么

\tilde{\mu}(x) = \prod_{i = 1}^{\infty}\left(1 - \frac{1}{p_i^x}\right)=\prod_{i = 1}^{\infty}\frac{p_i^x - 1}{p_i^x} = \frac{1}{\zeta(x)} \tilde{\mu^2}(x) = \prod_{i=1}^\infty\left(1 + \frac{1}{p^x}\right) = \prod_{i=1}^\infty\frac{p^x+1}{p^x} = \frac{\zeta(x)}{\zeta(2x)}

定义 n = \prod_{i=1}^mp_i^{k_i}\,,\,f(n) = \sum_{i=1}^m k_i\,,\,\lambda(n) = (-1)^{f(n)}。

\tilde{\lambda}(x) = \prod_{i=1}^\infty\sum_{i=0}^\infty p_i^{-ax}(-1)^a = \prod_{i=1}^\infty\frac{p^x}{p^x + 1} = \frac{\zeta(2x)}{\zeta(x)}

狄利克雷卷积与 DGF 的关系

对于数论函数 f,g,h，满足 f * g = h \iff \tilde{f} \times \tilde{g} = \tilde{h}。

证明：

当 f * g = h 时，有：

\begin{aligned} \tilde{h} &= \sum_{i = 1}^\infty\frac{h(i)}{i^x}\\ &= \sum_{i = 1}^\infty\sum_{d \mid n}\frac{f(d)}{d^x}\frac{g(\frac{i}{d})}{(\frac{i}{d})^x} \\ &= \sum_{d = 1}^\infty\sum_{j=1}^\infty\frac{f(d)}{d^x}\frac{g(j)}{j^x}\\ &=\tilde{f} \times \tilde{g} \end{aligned}

可以发现，上面证明的每一步都是等价变换，因此我们也完成了必要性的证明。

因此我们就能推出 \tilde{\sigma_{k}}(x) = \tilde{1} \times \tilde{\operatorname{id}_k} = \zeta(x)\zeta(x-k)。

例题：Sum of (-1)^f(n)\,。

Question

求 \sum_{i=1}^n\lambda(i)。

定义 f(n) = \sum_{i=1}^m k_i,\lambda(n) = (-1)^{f(n)}。

Solution

观察到 f 是完全和性函数，证明是显然的。

则 \lambda(a) \times \lambda(b)=(-1)^{f(a)+f(b)} = (-1)^{f(a \times b)} = \lambda(a \times b)，那么 \lambda 是完全积性函数。题目要求 \lambda 的前缀和，我们考虑杜教筛。

我们考虑写出 \tilde{\lambda}。

\tilde{\lambda} = \prod_{i=1}^\infty\sum_{i=0}^\infty p_i^{-ax}(-1)^a = \prod_{i=1}^\infty\frac{p^x}{p^x + 1} = \frac{\zeta(2x)}{\zeta(x)}

因为 \tilde{1} = \zeta(x)，我们考虑将 \lambda 与 1 做卷积。

记 h = \lambda * 1，则

h(p^k) = \sum_{d \mid p^k}(-1)^{f(d)} = \sum_{i=0}^k(-1)^i = [2 \mid k]

因为 h 为完全积性函数，所以 h(n) = [\,\exists \,d \in N^*,d^2=n]，\sum_{i=1}^nh(i) = \lfloor \sqrt{n} \rfloor。

那么 h 和 1 的前缀和都可以 O(1) 求出，直接杜教筛 \lambda 即可，时间复杂度 O(n^{\frac{2}{3}})。

声明

@henry_qwh 负责贝尔级数部分，@luuia 负责狄利克雷生成函数部分。