[SPOJ] DIVCNT2 - Counting Divisors (square)

题解：

操作挺多的一道题

网上证明挺多就不打了

$sigma_0(n^2) = sum_{dmid n} 2^{omega(d)} = sum_{dmid n} sum_{emid d} mu^2(e) = ((mu^2 * 1) * 1) (n)$

$(mu * 1) * 1 = mu * (1*1) = mu * sigma_0$

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

知道了这些按照杜教筛的套路处理$n^{frac{2}{3}}$就可以了