BZOJ 2440 [中山市选 2011] 完全平方数


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2440

题意:求第 k 个无平方因子数


首先直接求这个数是什么不是很容易... 考虑二分答案,问题转化为求 1-n 有多少个无平方因子数
这也是不好求的 但是我们知道 1-n 中有\(\frac{n}{i}\) 个数含有某因子 i 有重复 于是容斥
直接容斥的话是指数级别的 我们考虑对于因子 4 如果处理过 4 显然不需要处理 16
所以处理质因子即可
分别处理出现一个质因子、两个质因子、三个质因子... 的情况,发现容斥时的正负性恰好为\(\mu_i\)
(这是显然的... 由\(\mu_i\) 的定义得)
于是就结束了 二分复杂度\(log_k\),判断过程\(\sqrt k\) ,总复杂度\(O(log_k\sqrt k)\)

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 2440 [中山市选 2011] 完全平方数


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,