考虑求\(\sum_{i=1}^n\mu(i)^2\)
结论是\(\mu(i)^2=\sum_{j^2|i}\mu(j)\)
考虑证明这个式子。
先证明若\(\mu(i)\neq 0\)此时\(\mu(i)^2=1\)
显然只有\(j=1\)在右式造成贡献\(1\)等式成立。
若存在\(j\neq 1\)也在右式造成贡献，那么显然\(i\)有次数\(\ge 2\)质因子了\(\mu(i)=0\)与前面假设不符。
再考虑证明\(\mu(i)=0\)
设能对右式造成贡献的是质因子分别为\(k_1,k_2,...,k_m\)
那么显然\(j\)的取值有\(2^m\)种。
我们对\(j\)取不同的质因子个数分类那么右式的贡献为\(\sum_{v=0}^{m}(-1)^{v}C(m,v)\)
利用二项式定理合并\((1+(-1))^m=0\)
证毕。
则\(\sum_{i=1}^n\mu(i)^2=\sum_{j=1}^{\sqrt n}\mu(j)\cdot \lfloor\frac{n}{j^2}\rfloor\)
可以\(\sqrt n\)时间内求出。
进一步的考虑到\(\frac{n}{j^2}\)只有\(n^{\frac{1}{3}}\)种取值
只需预处理\(\mu(j)\)前缀和即可以在\(n^{\frac{1}{3}}\)求出，但是此时求前缀和已经是\(\sqrt n\)了就没必要再优化了。