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

吐槽:\(1\)难道不是完全平方数,那么这题就不用做了

首先显然是二分答案

那么如何求\(m\)以内的非完全平方数倍数个数呢?

假设我们把所有的完全平方数列出来,然后减去所有的它们的倍数

那么肯定有一些是重复的:即同时是多个完全平方数的倍数的数

于是就要容斥

那么我们观察一下,答案是

$$\frac{m}{1^2}-\frac{m}{2^2}-\frac{m}{3^3}-0\frac{m}{4^4}-\frac{m}{5^5}+\frac{m}{6^6}-…$$

每一项前面的系数正好是莫比乌斯函数

这也很好理解:对于质因数分解后有多个相同质数\(k\)的数\(s\),它的结果在统计\(s/k\)时已经统计过了,重复的也一起减掉了。

证明一下这个东西是对的:

对于拥有\(k\)个不同质因数的数\(s\),它在它的每一个拥有\(1\)个不同质因数的因子处被减了一次即\(-C_k^1\),在每一个拥有\(1\)个不同质因数的因子处被加了一次即\(C_k^2\)。。。

那么总共就是\(\sum_{i=1}^{k}(-1)^i C_k^i\)

由二项式定理,\(\sum_{i=1}^{k}(-1)^i C_k^i=-((-1)^0 C_k^0)=-1\)

就保证了每个数只减去一次

说点什么

  Subscribe  
提醒