原文链接。
约定
对于序列 \(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 为什么这么强啊。
标签:frac,zak,ln,质数,笔记,学习,sqrt,Theta,log From: https://www.cnblogs.com/zhouyuhang114/p/17609208.html