[SPOJ] DIVCNT2 - Counting Divisors (square)

46 阅读 0 评论 31 点赞

我是靠谱客的博主和谐红牛，最近开发中收集的这篇文章主要介绍[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}}$就可以了

转载于:https://www.cnblogs.com/yinwuxiao/p/10349446.html

以上就是和谐红牛为你收集整理的[SPOJ] DIVCNT2 - Counting Divisors (square)的全部内容，希望文章能够帮你解决[SPOJ] DIVCNT2 - Counting Divisors (square)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。