莫比乌斯函数的平方和

注意到 \mu(x)^2 在 x=p 的时候取值为 1，且在 x=p^c 的是偶取值为 0 且积性，因此可以 min-25。

这个太不优美了！

考虑杜教，我们随机尝试几个常见的积性函数，发现其和 \mu(x) 本身卷积的时候长的很趣味：得到的结果 h(x) 如果是完全平方数，则为 \mu(\sqrt{x}) 否则为 0。

因此 \sum_{i\le n} h(i) 其实就是 \sum_{i\le \sqrt{n}}\mu(i)，因此我们就可以杜教了！但是还要块筛 \mu。

这个常数太大了，有没有好一点的做法？继续试验会发现 \mu(x)^2 和 g(x)=[x=k^2] 卷起来是 ID，也就是当且仅当 x 是完全平方数的时候g 为 1。这个就更酷了，不过可能求 g 的前缀和有点慢的。

继续探讨更优秀的做法，有结论：

\sum_{i=1}^{n}\mu(i)^2=\sum_{j^2\mid i}\mu(j)

证明：考虑若 \mu(i)^2=1，则右侧只有一项 j=1（因为 i 无平方因子）否则说明其至少有一个质因子 p 出现了两次以上。

考虑将所有 j^2\mid i 分成两类：p 是 j 的因子/不是 j 的因子（由于 \mu(j) 不能为 0，因此 p 至多出现一次）。则两类 j 之间建立起一一对应关系，且对于每一对，它们的 \mu 互为相反数。因此这个 i 的贡献确实为 0。

这样，就可以直接计算这个式子了：

\sum_{i=1}^{n}\mu(i)\lfloor\frac{n}{i^2}\rfloor

可以看出，i 的取值上限是 \sqrt{n} 的，这样对于一个 n 可以 O(\sqrt{n}) 计算。

在块筛的时候也有优秀表现：类似杜教筛，直接暴力是 n^{\frac{3}{4}} 的，如果对 \le n^{\frac{2}{3}} 的直接线性筛预处理，则整体块筛的复杂度为 n^{\frac{2}{3}}。