对 μ^2 求前缀和的尝试
XeCtera
·
·
个人记录
(P9238)
记 \displaystyle{\rm S}f(n)=\sum_{i=1}^nf(i)，我们想求出 {\rm S}\mu^2(n) 的值。
**时间最优**
熟知 $\displaystyle {\rm S}\mu^2(n)=\sum_{i=1}^{\sqrt n}\mu(i)\left\lfloor\dfrac n{i^2}\right\rfloor$。
（开方默认下取整，下同）
考虑对 $\left\lfloor\dfrac n{i^2}\right\rfloor$ 进行整除分块，配合杜教筛求 ${\rm S}\mu$。
我们将需要 ${\rm S}\mu$ 在 $1\sim \sqrt[3]n,\sqrt{\dfrac n{\sqrt[3]n}}\sim\sqrt{\dfrac n1}$ 处的值。
设预处理范围为 $B$，则复杂度为
$$O\left(B+\sum_{i=1}^{n/B^2}\sqrt[4]{n/i}\right)=O\left(B+\dfrac n{B^{1.5}}\right)$$
取 $B=n^{0.4}$ 最优。
时间复杂度、空间复杂度均为 $O(n^{0.4})$。
**空间最优**
注意到另一个式子：$\displaystyle \sum_{i=1}^{\sqrt n}{\rm S}\mu^2\left(\dfrac n{i^2}\right)=n$。
直接将 $1\sim n$ 按最大平方因子 $i$ 分类即可证明。
和前面的式子大概只差一步容斥。
移项得到 $\displaystyle {\rm S}\mu^2(n)=n-\sum_{i=2}^{\sqrt n}{\rm S}\mu^2\left(\dfrac n{i^2}\right)$。
同样可以对 $n/i^2$ 整除分块。然后做和杜教筛类似的事情。
根据一条性质 $(n/i^2)/j^2=n/(ij)^2$，易知总共只用到 $O(n^{1/3})$ 个点值。
$$O\left(\sum_{i=1}^{\sqrt[3]n}\sqrt[3]{\dfrac n{i^2}}\right)=O(n^{4/9})$$
时间复杂度 $O(n^{4/9})$，空间复杂度 $O(n^{1/3})$。
**阴间寄巧**
使用一种离谱的方法，对做法二的空间进行卡常。
问题在于 ${\rm S}\mu^2$ 要用 long long 存。
我们知道 $\frac6{\pi^2}n$ 是 ${\rm S}\mu^2(n)$ 的一个非常好的近似。某道原神题的结论告诉我们，这误差非常小。
以至于我们可以用 16 位整型来强行存储 ${\rm S}\mu^2(n)$ 的值。内存开销变为原来的 $\frac14$。
那么如何还原出真实答案呢。
设真实的 ${\rm S}\mu^2(n)$ 为 $S$，而这样存储得到的为 $s$。
那么有 $S\equiv s\pmod{65536}$ 且 $|S-\frac6{\pi^2}n|\le 20000.
（后者来自那道原神题的结论。）
这样一来我们显然可以解出唯一确定的 S 值。就赢了。
说些什么
两种做法都可以通过调参来得到其他的时空复杂度。
做法一的空间复杂度最优是 O(n^{1/3})，此时的时间复杂度达到惊人的 O(\sqrt n)！
做法二的时间复杂度最优是 O(n^{3/7})，此时的空间复杂度也达到了 O(n^{3/7})。
都完全打不过另一种。
突发奇想，能否将两种做法结合起来，再次平衡呢？？
喜报，发现好像结合不了！！/oh
根号分治的败北。
唉，太神秘。
期待更加牛逼的做法。
upd on 2023 / 8 / 14
做法一可以用一些 Trick 优化到时间 O\left(\dfrac{n^{0.4}}{\log n}\right)，空间 O(n^{1/3})。
有空写一下代码。
upd on 2023 / 8 / 18
写了。