danihao123's Blog

给定$n$，分别求出$\mu(x^2)$和$\varphi(x^2)$的前$n$项和。

$1\leq n\leq 10^9$。

沿用约数个数和一题的思路……可以列出此式：

$$\sigma_1(ij) = \sum_{a | i}\sum_{b | j} ab[\gcd(\frac{i}{a}, b) = 1]$$

然后我们考虑去化简原式：

$$\begin{aligned} \sum_{i = 1}^n\sum_{j = 1}^n\sum_{a | i}\sum_{b | j} ab\sum_{d | \frac{i}{a}, d | j}\mu(d) \end{aligned}$$

接下来我们考虑枚举$d$，但是$a$和$b$的贡献又有点麻烦了……

$b$的贡献还好说，直接枚举$b$本身是$d$的多少倍就是$\sum_{b = 1}^{\lfloor\frac{n}{d}\rfloor} bd\lfloor\frac{n}{bd}\rfloor$。那$a$的贡献如何考虑？

我们考虑直接去枚举$a$本身……可以注意到一定有$a\le\lfloor\frac{n}{d}\rfloor$（因为$\frac{i}{a}\ge d$），所以直接枚举$a$本身之后再考虑$\lfloor\frac{n}{a}\rfloor$范围内$d$的倍数的数量即可（相当于找$\frac{i}{a}$），因此贡献为$\sum_{a = 1}^{\lfloor\frac{n}{d}\rfloor} a\lfloor\frac{n}{ad}\rfloor$。

那么继续化简原式：

$$\begin{aligned} \quad&\sum_{d = 1}^n\mu(d)\sum_{b = 1}^{\lfloor\frac{n}{d}\rfloor} bd\lfloor\frac{n}{bd}\rfloor\sum_{a = 1}^{\lfloor\frac{n}{d}\rfloor} a\lfloor\frac{n}{ad}\rfloor\\ =&\sum_{d = 1}^n\mu(d)d(\sum_{i = 1}^{\lfloor\frac{n}{d}\rfloor} i\lfloor\frac{n}{id}\rfloor)^2\\ =&\sum_{d = 1}^n\mu(d)d S_1^2(\lfloor\frac{n}{d}\rfloor) \end{aligned}$$

此处$S_1$表示$\sigma_1$的前缀和。

接下来预处理$\mu(d)d$的前缀和，考虑杜教筛。我们发现该函数和$\mathrm{id}$卷出来就是$\epsilon$（证明可以考虑贝尔级数……这种方式非常有效，并且还能帮我们找到需要卷的函数，我有时间会专门撰文写一下），所以杜教筛一波即可。这部分总复杂度为$O(n^{\frac{2}{3}})$。

至于$S_1$，我们考虑不大于$n^{\frac{2}{3}}$可以直接预处理，剩下的用时就用$O(\sqrt{n})$的方法求（考虑到反演不会用到$S_1$的重复状态所以不需要记忆化）。用类似于杜教筛复杂度证明的方法可以证明该部分总复杂度为$O(n^{\frac{2}{3}})$。

代码：