标签为 [容斥原理] 的文章

BZOJ2440 完全平方数(二分+容斥原理)

题目大意 有几组询问,每次询问第k大的不是完全平方数(1外的)倍数的数。 k<=1000,000,000 Solution 如果可以快速计算1~n区间内不是完全平方数的倍数的个数,这个答案就可以二分了。 令$ x0=ax^2$(x$ \in$ 质数,$ a\in\mathbb{N}$),将n减去x0的个数后发现,所有完全平方数倍数的数都被减去了,而有些这样的数被减了两次。 令$ x0=ax^2$(x=pq p$ \in质数 q \in$质数,$ a\in\mathbb{N}$),x0在上面被减了两次,再把它们加上。 …… 其实就是做容斥。 若x分解质因数后次数都是一,x有偶数个质因数,答案加上$ \frac{n}{x^2}$ 若x分 ......