Bzoj2440 完全平方数(莫比乌斯容斥)

题意：

找第k个不含完全平方数因子的数

题解：

二分+莫比乌斯系数+容斥

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
bool isprime[maxn];
int prime[maxn];
int mu[maxn];
void getMu()
{
	memset(isprime,1,sizeof(isprime));
	mu[1]=1;
	int tot=0;
	for(int i=2;i<=maxn;i++)
	{
		if(isprime[i])
		{
			 prime[++tot]=i,mu[i]=-1;
//			 cout<<tot<<" "<<prime[tot]<<endl; 
		}
		for(int j=1;j<=tot&&prime[j]*i<=maxn;j++)
		{
			isprime[i*prime[j]]=0;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;
				break;
			}
			else mu[i*prime[j]]=-mu[i];	
		}
	 } 
}
long long check(int n)
{
	int t=sqrt(n);
	long long sum=0;
	for(int i=1;i<=t;i++)
	{
		sum+=n/(i*i)*mu[i];
	}
//	cout<<n<<" "<<sum<<endl;
	return sum;
}

int main()
{
	int T,n,m,i,j,k;
	scanf("%d",&T);
	long long l,r,ans;
	getMu();
//	for(int i=0;i<=T;i++)	cout<<i<<" "<<mu[i]<<" "<<prime[i]<<endl;
	while(T--)
	{
		scanf("%d",&k);
		l=k,r=1644934081;
		while(l<=r)
		{
			long long mid=(l+r)>>1;
			if(check(mid)>=k) ans=mid,r=mid-1;
			else l=mid+1;
		}
		printf("%lld\n",ans);
	}
}

Q.E.D.