卷个积吧。

XeCtera · 2023-08-12 20:35:24 · 题解

题目传送门：P9511 『STA - R3』大豆

0. 前言

给出一种时间复杂度 O\left(\dfrac{km^{3/4}}{\log m}\right)，空间复杂度 O(\sqrt m) 的做法。

常数较小且不难实现。

1. 记号约定

记 \displaystyle {\rm S}f(n)=\sum_{i=1}^nf(i)。

记 x/y=\lfloor\frac xy\rfloor，且运算优先级低于乘法，即 x/yz 表示 x/(yz)。

2. 题解 (Part 1)

不难发现 \{a\} 的大豆化序列 \{b\} 满足

注意到这与杜教筛使用的式子具有相似性。

具体地，设 I(n)=1 为常函数，g*I=f，则

当此式成立时，显然也能反推出 g*I=f。

本题中只需令 f,g 分别为 \{a\},\{b\} 的差分，那么有 g=f*\mu。

所求即为 {\rm S}(f*\mu^k)(m) 的值。（\mu^k 表示 k 个 \mu 卷积的结果）

使用足够厉害的数论科技即可解决。

下面开始介绍科技。

3. Dirichlet 双曲线法

这里可以把它当成整除分块的替代品。

相比于整除分块，它在常数等方面有一定优势。

考虑求如下式子的值：

（假设 f,g,{\rm S}f,{\rm S}g 的点值都可以 O(1) 得到）

设阈值 x,y 满足 xy=n。

我们对 i\le x 的部分和 j\le y 的部分分别求和，再减去公共部分。

可以 O(x+y) 完成计算。

通常取 x=y=\sqrt n 得最优复杂度 O(\sqrt n)。

4. 块筛卷积

首先我们有一条重要性质：x/y/z=x/yz。

根据这条性质，再结合整除分块的一些分析可知：

在求 {\rm S}f(n) 时，我们往往只需用到 {\rm S}f(1)\sim {\rm S}f(\lfloor\sqrt n\rfloor),{\rm S}f(n/\lfloor\sqrt n\rfloor)\sim{\rm S}f(n/1) 的值。

称之为 f（在 n 处）的块筛。

块筛卷积：假设有一个狄利克雷卷积式 f*g=h，其中 f,g 的块筛已知，试求 h 的块筛。

可以直接用 Dirichlet 双曲线法，对块筛的每个位置暴力求解。

（开方运算默认下取整，下同）

复杂度是 \displaystyle O\left(\sum_{i=1}^{\sqrt n}\sqrt i+\sum_{i=1}^{\sqrt n}\sqrt{n/i}\right)=O(n^{3/4})。

可以进一步优化，但这里暂且不提。

5. 杜教筛

假设有一个狄利克雷卷积式 f*g=h，其中 g,h 的块筛已知，试求 f 的块筛。

事实上前面的做法仍然适用，只需要对式子做个移项：

递推即可，复杂度同样为 O(n^{3/4})。（同样可以优化，但先不提）

这种方法通常被称为杜教筛。

若使用普通数组存储块筛，并像上面这样递推求解，这种实现或许可以称为 dp 式杜教筛。

目前广为流传的则是递归 + map / unordered_map 记忆化存储的写法。我暂且称之为记搜式杜教筛。

事实上 dp 式实现的常数要小很多，并且复杂度也更加直观。

不明白为什么大家都用记搜式。难过。

6. 整除运算的优化

底层卡常技巧。

预处理 1\sim\sqrt m 的倒数，将整除改为浮点乘。

若实现得当，可以保证代码中所有整除运算的除数都在 1\sim\sqrt m 以内。将会有良好的优化效果。

注意事项：

用 (1+1e-15)/x 这样的方式来计算 x 的倒数，而非 1./x 。后者的精度损失可能导致出错。

7. 题解 (Part 2)

回到本题，我们要求 {\rm S}(f*\mu^k)(m) 的值，其中 f 的块筛已知。

朴素做法是对 f 做 k 次杜教筛。

事实上，dp 式杜教筛 + 整除优化的实现已经能够以 O(km^{3/4}) 的复杂度通过。

并且应该可以吊打 std。

但这还不够令人满意。下面给出一种更优秀的做法。

注意到 \mu 是积性函数，比 f 具有更好的性质。

考虑先求 \mu^k 的块筛，然后容易 O(\sqrt m) 得到 {\rm S}(f*\mu^k)(m)。

对于积性函数 f，记 f_j(n)=f(n)[{\rm minp}(n)>p_j]。

其中 {\rm minp}(n) 是 n 的最小质因子（钦定 {\rm minp}(1)=+\infty），p_j 是第 j 个质数。

取阈值 K 满足 p_{K+1} 略大于 \sqrt[4]m，那么 f_K 有优秀的性质：