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

发布于 2017-06-14  183 次阅读


题目链接: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)\)

 


一个非常弱的准退役OIER