[SPOJ] DIVCNT2

题解:

操作挺多的一道题

网上证明挺多就不打了

$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} floor$

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

 

原文地址:https://www.cnblogs.com/yinwuxiao/p/10349446.html