SP4168
jijidawang
·
·
题解
纯代数做法！不依赖任何容斥等组合意义。首次公开于 joke3579 闲话 22.12.18。
答案就是 \mu^2 前缀和，于是
\begin{aligned}
&\sum_{i=1}^n \mu^2(i)
\\ = & \sum_{i=1}^n \sum_{d|i} \sum_{e|d} \mu(e)\mu^2\left(\frac de\right)
\\ = & \sum_{i=1}^n \sum_{d|i} \sum_{e|q} \mu(pe)\mu^2\left(\frac {p^2q}{pe}\right)&\text{where }d = p^2 q,\,p\perp q
\\ = & \sum_{i=1}^n \sum_{d|i} \sum_{e|q} \mu(p)\mu(e)\mu^2\left(p\right)\mu^2\left(\frac {q}{e}\right)
\\ = & \sum_{i=1}^n \sum_{d|i} \mu^3(p) \sum_{e|q} \mu(e)\mu^2\left(\frac {q}{e}\right)
\\ = & \sum_{i=1}^n \sum_{d|i} \mu(p) \sum_{e|q} \mu(e)
\\ = & \sum_{i=1}^n \sum_{d|i} \mu(p) [q = 1]
\\ = & \sum_{i=1}^n \sum_{p^2|i} \mu(p)
\\ = & \sum_{p = 1}^{\left\lfloor\sqrt n\right\rfloor }\left\lfloor\frac n{p^2} \right\rfloor \mu(p)
\end{aligned}
整除分块计算，时间复杂度 \Theta(\sqrt n+T\sqrt[4]n)，可以通过。