【中山市选2011】完全平方数

Source and Judge

bzoj2440

Record

30min

Analysis

请先思考后再展开

市选时代的题目,挺妙的
就是你先考虑这种数怎么贡献到单一约数上
然而即使你去除那些因子数>1的约数,你发现并不只一个,然而这是可以容斥的
然后你发现mu既能去除平方因子,又能帮你容斥
然后你需要枚举的地方只有根号级别,mu可以用线性筛处理出来
所以最后套个二分就好了,这个倒比较显然

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/d03f.html
转载请注明出处,谢谢!