数论 整除分块 SP20174题解

· · 题解

设 f_k(n)=\sigma_0(n^k)，考虑 PN 筛。

有 f_k(p)=k+1=f_{k-1}(p)+f_{k-1}(1)。

也就是说设 g_k=\mu^2 * f_{k-1}，有 g_K(p^k)=Kk+1+K(k-1)+1=K(2k-1)+1。

然后可以直接把 h_K 给暴力卷出来。（因为 g_K,f_K 和 h_K 都和 p 没有关系，所以只需要卷一次）

考虑如何求 \mu^2 * f_{k-1}。如果我们知道了 f=g * h，以及 g 和 h 的块筛（在集合 \lfloor\frac{n}{i}\rfloor 处的前缀和），显然可以来一个 n^{\frac{3}{4}} 计算 f 的块筛。如果加上线性筛预处理可以做到 O(n^{\frac{2}{3}})。

对于 \mu^2 的前缀和，我们设 mxs(n) 表示 n 的最大平方质因子，那么有：

\sum_{i=1}^{n}[mxs(i)=1] \sum_{i=1}^{n}\sum_{d\mid mxs(i)}\mu(d) \sum_{d=1}^{\sqrt{n}}\mu(d)\lfloor\frac{n}{d^2}\rfloor

于是我们可以 O(\sqrt{n}) 计算 \mu^2 在单点处的前缀和，配合线性筛预处理可以做到 O(n^{\frac{2}{3}}) 预处理 \mu^2 的块筛。

接下来需要干的就是计算 f_{k-1} 的块筛。容易发现这个也可以使用 PN 筛计算。

使用 PN 筛计算 f_3 和 f_2，对于 f_1 显然可以整除分块+线性筛处理其块筛。

复杂度 O(\sum n^{\frac{2}{3}})。

啊其实，容易发现有 f_2=\mu^2 * \sigma，所以 f_2 就没必要上 PN 筛了 qwq。