推导的工具¶
贝尔级数¶
构造杜教筛有点太难了！考虑类似多项式计数那样，用一个无穷级数来刻画数论函数的狄利克雷卷积。
我们说，积性函数 \(f\) 对于质数 \(p\) 的贝尔级数定义为
\[
F_p(z)=\sum_{k\ge 0}f(p^k)z^k
\]
显然对每个质数 \(p\)，这个多项式在常识数据范围下都只有 \(\mathcal O(\log n)\) 项，对其直接进行暴力的多项式操作是可行的。而两个函数的贝尔级数的乘法就对应数论函数的狄利克雷卷积。
那么很快我们就能写出一批常见数论函数的贝尔级数
\[
\begin{aligned}
&\epsilon(n) \longrightarrow E_p(z)=1 \\
&\mathbf{I}(n)\longrightarrow I_p(z)=\frac{1}{1-z}\\
&\mu(n)\longrightarrow \mathrm{M}_p(z)=1-z\\
&\mu^2(n)\longrightarrow \operatorname{M}^2_p(z)=1+z\\
&\varphi(n)\longrightarrow \Phi_p(n)=1+\qty(1-\frac{1}{p})\sum_{i\ge 1}p^iz^i=\frac{1-z}{1-pz}\\
&\operatorname{id}^k(n)\longrightarrow \operatorname{ID}^k(n)=\sum_{i\ge 0}p^{ik}z^i=\frac{1}{1-p^kz}\\
&\operatorname{}
\end{aligned}
\]