扩展 PN 筛 & 平方卷积

· · 算法·理论

View it on my blog :)

一个 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

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

2

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

3

考虑将 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})。