[BZOJ2440][中山市选2011]完全平方数(莫比乌斯反演,二分)

发布于 2018-01-21  10 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2440][中山市选2011]完全平方数(莫比乌斯反演,二分)

Description

小 X 自幼就很喜欢数。但奇怪的是,他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此,他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。
这天是小X的生日,小 W 想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数,然后选取了第 K个数送给了小X。小X很开心地收下了。
然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗?

Http

BZOJ

Tag

莫比乌斯反演,二分

解决思路

先考虑二分,把题目变成判定问题,即询问在某个范围内,不包含完全平方数因子的数有多少个。
一个数不包含完全平方数,那么就是说唯一分解后没有任何一个质数的质数超过\(1\)。
容斥一下,那么答案就是
Ans-至少一个质因子个数大于1+至少两个质因子个数大于1-至少三个质因子个数大于1-至少四个质因子个数大于1
考虑每一个数对这个式子的贡献,呃,不就是\(\mu()\)吗?
那么线性筛出\(\mu\),二分答案求解就可以啦!

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2440][中山市选2011]完全平方数(莫比乌斯反演,二分)


HNCJ OIer 一枚