【BZOJ 2440】【中山市选 2011】完全平方数 莫比乌斯函数+容斥原理

网上PoPoQQQ的课件：

•题目大意：求第k个无平方因子数

•无平方因子数(Square-Free Number)，即分解之后所有质因数的次数都为1的数

•首先二分答案 问题转化为求[1,x]之间有多少个无平方因子数

•根据容斥原理可知 对于sqrt(x)以内所有的质数 有

•  x以内的无平方因子数

•=0个质数乘积的平方的倍数的数的数量(1的倍数)

•-每个质数的平方的倍数的数的数量(9的倍数,25的倍数,...)

•+每2个质数乘积的平方的倍数的数的数量(36的倍数,100的倍数,...)-...

每个乘积$a$前的符号恰好是$\mu(a)$(这点很关键)

$x$以内$i^2$的倍数有$\left \lfloor \frac{x}{i^2} \right \rfloor$个，所以$Q(x)=\sum_{i=1}^{\left \lfloor \sqrt{x} \right \rfloor} \mu(i) \left \lfloor \frac{x}{i^2} \right \rfloor$

像上面说的那样，二分一下$x$查找第$k$小的$x$即可

#include<cmath>
#include<cstdio>
using namespace std;
typedef long long LL;
const int MAXN=50003;
int p[MAXN],pcnt=0,mu[MAXN],n;
bool notp[MAXN];
void shai(){
	mu[1]=1;
	for(int i=2;i<=50000;++i){
		if (notp[i]==0){
			p[++pcnt]=i;
			mu[i]=-1;
		}
		for (int j=1,t=p[j]*i;j<=pcnt&&t<=50000;++j,t=p[j]*i){
			notp[t]=1;
			if (i%p[j]==0){
				mu[t]=0;
				break;
			}else
				mu[t]=-mu[i];
		}
	}
}
LL work(LL x){
	LL s=0; int t=sqrt(x);
	for(int i=1;i<=t;++i)
		s+=x/(i*i)*mu[i];
	return s;
}
int main(){
	shai();
	int T;
	LL K,left,right,mid;
	scanf("%d",&T);
	while (T--){
		scanf("%lld",&K);
		left=K; right=1644934081;
		while (left<right){
			mid=(left+right)>>1;
			if (work(mid)>=K) right=mid;
			else left=mid+1;
		}
		printf("%lld\n",left);
	}
	return 0;
}

这样就行啦