扩展 PN 筛 & 平方卷积

一个 PN 筛拓展，idea 来自 $\mu^2$ 前缀和。文中大写字母代表对应小写字母函数的前缀和。

$k\text{-PN}$

定义。 对正整数 $n,k$，设 $n$ 的质因数分解为 $n=\prod_i p_i^{e_i}$（$e_i>0$），若对任意 $i$ 都有 $e_i\ge k$，称 $n$ 为 $k\text{-PN}$。

考虑将 $k\text{-PN}$ 也用类似 $a^2b^3$ 的形式表示。

引理。 $k\text{-PN}$ 可以唯一写成 $\prod_{i=0}^{k-1}a_i^{k+i}$ 的形式，其中 $a_1,\dots,a_{k-1}$ square free 且两两互质。

证明。 依次考察 $k\text{-PN}$ 的素因子 $p^e$，令 $a_0\gets a_0\cdot p^{\lfloor e/k\rfloor -1}$，$a_{e\bmod k}\gets a_{e\bmod k}\cdot p$。由于 $k(\lfloor e/k\rfloor-1)+(k+e\bmod k)=e$，显然得证。同时易得 $a_1,\dots,a_{k-1}$ square free 且两两互质。

从这个引理容易得到 $k\text{-PN}$ 的数量。

定理。 对固定的 $k$，不超过 $N$ 的 $k\text{-PN}$ 个数的数量级为 $\Theta(N^{1/k})$。

证明。 下界是显然的：所有 $a^k$ 都是 $k\text{-PN}$。上界： $$ \begin{aligned} |\{n\le N: n\text{ is }k\text{-PN}\}| &\le\sum_{a_1,\dots,a_{k-1}}\left(\frac{N}{\prod_{j=1}^{k-1}a_j^{j+k}}\right)^{1/k}\\ &\le N^{1/k}\prod_{j=1}^{k-1}\zeta(1+j/k)\\ &=O(N^{1/k}) \end{aligned} $$

ex-PN 筛

对积性函数 $f$，考虑构造积性函数 $g$ 使得对任意 $p$ 和 $j=1,2,\ldots,k-1$ 都有 $f(p^j)=g(p^j)$。令 $h=f/g$（Dirichlet 卷积除法）。由 Dirichlet 卷积容易知道 $h(p^j)=0$，因此 $h$ 仅在 $k\text{-PN}$ 上有值。套用 PN 筛的方法即可。

此时求 $g$ 的前缀和变成主要瓶颈，设求 $g$ 的前缀和复杂度为 $\widetilde O(N^{\alpha})$，则求 $f$ 的复杂度为 $\widetilde O(N^{\max(\alpha,1/k)})$。故增加 $k$ 意义不大。一般可以取 $k=3$，并寻找容易求和的 $g$。下面给出一种基于 $g(p)=f(p),g(p^2)=f(p^2)$ 的方法。

$g$

考虑以下两个数论函数：完全积性函数 $w(p)=f(p)$；积性函数 $v(p)=f(p^2)$，高次幂视情况选取。然后构造： $$ g(p^{2e})=v(p^e),\quad g(p^{2e+1})=w(p)v(p^e) $$ 考虑将每个 $n$ 写成 $n=ab^2$ 的形式，其中 $a$ square-free，显然这种写法是唯一的，那么有 $g(n)=w(a)v(b)$。故有 $$ \begin{aligned} G(N) &=\sum_{ab^2\le N}\mu^2(a)w(a)v(b)\\ &=\sum_{b\le \sqrt N}v(b)\sum_{a\le N/b^2}\mu^2(a)w(a)\\ &=\sum_{b\le \sqrt N}v(b)\sum_{d^2m\le N/b^2}\mu(d)w(d^2m)\\ &=\sum_{b\le \sqrt N}v(b)\sum_{d\le\sqrt{N/b^2}}\mu(d)w^2(d)W\left(\left\lfloor\frac{N}{b^2d^2} \right\rfloor\right) \end{aligned} $$ 令 $u=v*(\mu\cdot w^2)$，则 $$ G(N)=\sum_{c\le \sqrt N}u(c)W\left(\left\lfloor\frac{N}{c^2}\right\rfloor\right) $$ 有 $u(p)=f(p^2)-f^2(p)$。莫反告诉我们 $v=u*w^2$！所以可以杜教筛 $U$ 前缀和。这里的复杂度平衡类似筛 $\mu^2$ 的方法：如果 $W$ 和 $w^2$ 前缀和都能 $O(1)$ 求，假设求 $V$ 复杂度为 $O(N^{\beta})$（$1/2\le \beta<1$），那么把 $u$ 筛到 $N^{1/(3-\beta)}$，总复杂度就是 $\widetilde O(N^{1/(3-\beta)})$ 的。一般而言能够得到一个 $o(\sqrt N)$ 的求和方法。

平方卷积

看起来这个 $G$ 是降低复杂度的关键。发现这个 $G$ 其实相比 Dirichlet 卷积，只是把条件从 $ab=n$ 改成了 $ab^2=n$。我们考虑定义一个这样的卷积，暂且叫它“平方卷积”：

$$ f(n)=(u\ast_2 v)(n)=\sum_{ab^2=n}u(a)v(b) $$

注意平方卷积不满足交换律。平方卷积容易转换成 Dirichlet 卷积的形式。只需要令 $v'$： $$ v'(n)=\begin{cases} v(b) & n=b^2\\ 0 & \text{otherwise} \end{cases} $$ 那么就有 $u\ast_2 v=u\ast v'$。

对平方卷积的结果做一下 Dirichlet 双曲线法，令截断处 $A=\lfloor N/B^2\rfloor$，有 $$ F(N)=\sum_{a\le A}u(a)V\left(\left\lfloor\sqrt\frac{N}{a}\right\rfloor\right)+\sum_{b\le B}v(b)U\left(\left\lfloor\frac{N}{b^2}\right\rfloor\right)-U(A)V(B) $$ 当 $B=\Theta(N^{1/3})$ 时总项数为 $O(N^{1/3})$，看起来比较容易求。

Revisit ex-PN

直接将 $f$ 分解成平方卷积可能不容易，但是 PN 筛的思想告诉我们，只要找到一个能分解的 $g$，并且前几项能拟合 $f$ 就行。

还是考虑拟合 $p$ 和 $p^2$ 处的值，那么取积性函数 $u(p)=f(p),v(p)=f(p^2)-u(p^2)$，并令 $g=u\ast_2 v$ 即可。

Examples

1

$f(p^e)=p^r$。

在扩展 PN 筛中构造 $w=v=\mathrm{id}_r$ 即可，$\widetilde O(N^{2/5})$。

2

$f(p^e)=pe$。

在扩展 PN 筛中构造 $w=\mathrm{id},v=\mathrm{id}\ast\mathrm{id}$ 即可，$\widetilde O(N^{2/5})$。

3

$f(p^e)=p^e+1$。

考虑将 $f$ 用平方卷积分解。

考察 $\sigma(p^e)=1+p+\cdots+p^e$，直观地有 $f(p^e)=\sigma(p^e)-p\sigma(p^{e-2})$。再令 $h$： $$ h(p^e)=\begin{cases} 1 & e=0 \\ -p & e=2 \\ 0 & \text{otherwise} \end{cases} $$ 那么有 $f=\sigma\ast h$。这个 $h$ 容易转换成平方卷积：令 $g=\mu\cdot \mathrm{id}$ 就有 $f=\sigma\ast_2 g$。而 $\sigma$ 和 $g$ 的前缀和都容易求（前者需要 DIVCNT1），直接做就行。复杂度算下来是 $\widetilde O(N^{3/7})$。