zak 筛学习笔记

原文链接。

约定

对于序列 \(a\)，其在 \(n\) 处的块筛指的是对于所有不同的 \(x=\left\lfloor\frac{n}{k}\right\rfloor\)，求出 \(S_a(x)=\sum_{i=1}^xa(i)\)。由于不同的 \(\left\lfloor\frac{n}{k}\right\rfloor\) 只有 \(\Theta(\sqrt n)\) 个，从而块筛的信息量是 \(\Theta(\sqrt n)\) 的。

\(\times\) 均指 \(\operatorname{Dirichlet}\) 卷积，\(a^k\) 即为 \(\operatorname{Dirichlet}\) 卷积的 \(k\) 次幂。

块筛卷积

整个算法的核心在于解决以下问题：

（块筛卷积）给定序列 \(a,b\) 在 \(n\) 处的块筛，求出 \(a\times b\) 在 \(n\) 处的块筛。

对于这一问题，朴素的整除分块可以做到 \(\widetilde{O}(n^{2/3})\)。zak 给出了一个 \(\Theta(\sqrt n\log^2n)\) 的做法。

注意到，此前的做法是对块筛点值处的 \(z\)，利用 \((a\times b)(z)=\sum_{xy=z}a(x)b(y)\) 推导并使用整除分块优化。现在我们摒弃这一思路，转而去计算每一对 \((x,y)\) 对答案的贡献。

• 当 \(\max(x,y)>\sqrt n\) 时：

  不妨设 \(x>\sqrt n\)，则有 \(y<\sqrt n\)。注意到 \(a(x)b(y)\) 只会对块筛中的 \(\left\lfloor\frac{n}{1}\right\rfloor,\left\lfloor\frac{n}{2}\right\rfloor,\cdots,\left\lfloor\frac{n}{\lfloor n/xy\rfloor}\right\rfloor\) 产生贡献；换言之，\(a(x)b(y)\) 对块筛产生的贡献只和 \(\left\lfloor\frac{n}{xy}\right\rfloor\) 有关。而 \(\left\lfloor\frac{n}{xy}\right\rfloor=\left\lfloor\frac{\lfloor\frac{n}{x}\rfloor}{y}\right\rfloor\)。不妨记 \(t=\left\lfloor\frac{n}{x}\right\rfloor\)，则对于固定的 \(t\)，所有这样的 \(x\) 的 \(a(x)\) 之和恰为 \(S_a\left(\left\lfloor\frac{n}{t}\right\rfloor\right)-S_a\left(\left\lfloor\frac{n}{t+1}\right\rfloor\right)\)。又注意到，所有 \(\left\lfloor\frac{t}{y}\right\rfloor=k\) 的 \(t\) 构成一段区间 \([ky,(k+1)y)\)，因此我们只需枚举 \(y,k\)，直接计算贡献复杂度即为 \(\Theta(\sqrt n\log n)\)。

• 当 \(\max(x,y)\le \sqrt n\) 时：

  • 当 \(xy\le \sqrt n\) 时：

    暴力枚举 \(x,y\)，并直接贡献即可。复杂度 \(\Theta(\sqrt n\log n)\)。

  • 当 \(xy>\sqrt n\) 时：

    同样，\(a(x)b(y)\) 对块筛的贡献只和 \(\left\lfloor\frac{n}{xy}\right\rfloor\) 有关。 注意到 \(\left\lfloor\frac{n}{xy}\right\rfloor\) 为最大的满足 \(xy\le \frac{n}{t}\) 的 \(t\)。

    以下是最关键的一步：对不等式两侧同时取 \(\ln\)，则有 \(\ln x+\ln y\le \ln \frac{n}{t}\)。于是，我们得到了一个形似和卷积的形式。不妨在两侧同时乘上一个 \(B\)，就有 \(B\ln x+ B\ln y\le B \ln \frac{n}{t}\)。我们考虑先计算出一部分的贡献，即将左侧上取整，将满足 \(\lceil B\ln x \rceil + \lceil B\ln y\rceil \le B \ln \frac{n}{t}\) 的 \((x,y)\) 的贡献先行计算出来。这就是一个标准的和卷积形式了，具体而言，算出 \(F(x)=\left(\sum_{i=1}^{\sqrt n}a(i)x^{\lceil B\ln i\rceil}\right)\times\left(\sum_{i=1}^{\sqrt n}b(i)x^{\lceil B\ln i\rceil}\right)\)，并将每一个 \([x^i]F\) 贡献到对应的 \(t\) 的位置（特别的，如果对应的 \(t\ge\sqrt n\) 说明 \(xy\le\sqrt n\)，则不应再贡献），最后做前缀和即可。由于 \(B\ln i\) 的值域为 \(B\log n\)，从而总复杂度为 \(\Theta(B\log^2 n)\)。

    现在处理那些被我们漏掉的部分。注意到，这样的 \((x,y)\) 一定满足 \(B\ln x+B\ln y\le B\ln \frac{n}{t}< \lceil B\ln x \rceil + \lceil B\ln y\rceil\)，从而 \(B\ln \frac{n}{t}-B\ln x-B\ln y<2\)，移项即有 \(\ln n-\ln (xyt)<\frac{2}{B}\)。由于 \(\frac{\text d\ln x}{\text dx}=\frac{1}{x}\)，从而 \(\frac{1}{n}\le \frac{\ln n - \ln(xyt)}{n-xyt},n-xyt< \frac{2n}{B}\)。于是我们只需要对 \((n-\frac{2n}{B},n]\) 区间筛得到所有数的质因数分解，进而搜出所有满足要求的 \((x,y,t)\) 即可。区间筛部分的复杂度为 \(\Theta(\frac{n}{B}\log n)\)，而根据原文中 \(\sum_{xyz\le n}1=nP_3(\ln n)+O(n^{43/96+\varepsilon})\) 的结论（其中 \(P_3\) 为二次多项式），容易看出 \(\sum_{n-\frac{2n}{B}\le xyz\le n}1=\Theta(\frac{n}{B}\log^2n)\)。

    现在，我们只需取 \(B=\sqrt n\)，就得到了这一部分的最优复杂度 \(\Theta(\sqrt n\log^2 n)\)。

于是，我们在 \(\Theta(\sqrt n\log^2 n)\) 的复杂度内解决了上述问题。

应用

我们考虑将上述算法应用到一般性的积性函数块筛中。

算法的大致思路较为明确：欲求 \(f\) 的块筛，则先将 \(f(p)\) 处取值拆成 \(k\) 个简单积性函数（需要保证其块筛容易求出）之和。接下来，我们来分别解决两个问题。

• 已知 \(f\) 的质数处块筛，求 \(f\) 的块筛：

  设 \(g\) 满足 \(g(n)=[n\in \mathbb P]f(n)\)，所谓 “质数处块筛” 指的即是 \(g\) 的块筛。注意到 \(g\) 并非积性函数，但是如果我们考虑 \(g\) 的 “\(\exp\)"：\(h=\sum_{i\ge0}\frac{g^i}{i!}\)，我们会惊奇的发现：

  • 由于 \(g(1)=0\)，从而这一行为是良定义的。
  • \(h(p^k)=\frac{f(p)^k}{k!}\)。
  • \(h\) 是积性函数。

  前两点很容易理解，而关于第三点，一个比较简单的证明是：由于 \(g\) 只在质数处有值，则从组合意义出发不难发现 \(h\left(\prod_{i=1}^k p_i^{\alpha_i}\right)=\frac{\prod_{i=1}^kg\left(p_i^{\alpha_i}\right)}{\prod_{i=1}^k\left(\alpha_i!\right)}\)，且 \(h(1)=1\)，而这显然是一个积性函数。

  由于我们已经知道 \(g\) 的块筛，而 \(h=\sum_{i=0}\frac{g^i}{i!}\) 中的 \(i\) 在求其在 \(n\) 处块筛时只用枚举到 \(\Theta(\log n)\)，那么应用此前 \(\Theta(\sqrt n\log^2 n)\) 的块筛卷积算法即可在 \(\Theta(\sqrt n\log^3 n)\) 的复杂度内得出 \(h\) 的块筛。接下来，由于 \(h(p)=f(p)\)，从而 \(f\times h^{-1}\) 只在 PN 处有值。于是，我们只需求出 \(f\times h^{-1}\) 的块筛，并将其卷上 \(h\) 的块筛即可得到 \(f\) 的块筛。而 \(f\times h^{-1}\) 只有 \(\Theta(\sqrt n)\) 个位置有值，很容易在 \(\Theta(\sqrt n\log n)\) 复杂度内得到其块筛。于是这一部分的总复杂度即为 \(\Theta(\sqrt n\log^3 n)\)。

• 已知 \(f\) 的块筛，求 \(f\) 的质数处块筛：

  注意到这个问题是上面问题的逆，我们只需将上面的步骤倒过来：

  • 通过卷上一个只在 PN 处有值的函数，得到积性函数 \(h(p^k)=\frac{f(p)^k}{k!}\) 的块筛。
  • 求出 \(h\) 的 "\(\ln\)"：\(g=\sum_{i\ge 1}(-1)^{i-1}\frac{(h-\varepsilon)^i}{i}\)。与 ”\(\exp\)" 类似，由于 \((h-\varepsilon)(1)=0\)，因此这一行为是良定义的，且 \(i\) 只需枚举至 \(\Theta(\log n)\) 位置。从组合意义出发同样可以证明 \(g\) 只在质数处有值，且 \(g(p)=h(p)=f(p)\)。于是，我们同样只用做 \(\Theta(\log n)\) 次块筛卷积即可得到 \(g\) 的块筛，即 \(f\) 的质数处块筛。复杂度同样为 \(\Theta(\sqrt n\log^3 n)\)。

现在，我们只需延续最初的大致思路即可。对于拆出的 \(k\) 个简单积性函数，首先求出其块筛，然后用上述方法得到它们的质数处块筛。接下来，由于在质数处 \(f\) 的取值等于这 \(k\) 个积性函数之和，从而将这 \(k\) 个块筛相加即可得到 \(f\) 的质数处块筛。最后运用上述方法，即可得到 \(f\) 的块筛。由于 \(f\) 被拆分成 \(k\) 个简单积性函数，因此最终复杂度为 \(\Theta(k\sqrt n\log^3 n)\)。

后记

zak 为什么这么强啊。