题目大意：求第k个无平方因子数是多少(无视原题干。1也是全然平方数那岂不是一个数也送不出去了？

无平方因子数(square-free number)，即质因数分解之后全部质因数的次数都为1的数

首先二分答案 问题转化为求x以内有多少个无平方因子数

依据容斥原理可知 对于√x以内的全部质数 x以内的无平方因子数=无需是不论什么质数的倍数的数的数量(即x)-是至少一个质数平方倍数的数的数量+是至少两个质数平方倍数的数的数量-是至少三个质数平方倍数的数的数量...

我们回去考虑莫比乌斯函数，我们发现每个质数乘积的符号与莫比乌斯函数的符号恰好吻合！

于是我们枚举每个数，假设这个数是奇数个不同质数的乘积，那么mu为负，偶数个则mu为正。否则mu为零

故答案即Σx/(i*i)*mu[i]

大早上起来连线性筛都打不正确我也是醉了。。。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define M 44723

using namespace std;

int mu[M]={0,1},prime[M],tot;

bool not_prime[M];

void Linear_Shaker()

{

	int i,j;

	for(i=2;i<M;i++)

	{

		if(!not_prime[i])

			mu[i]=-1,prime[++tot]=i;

		for(j=1;prime[j]*i<M;j++)

		{

			not_prime[prime[j]*i]=1;

			if(i%prime[j]==0)

			{

				mu[prime[j]*i]=0;

				break;

			}

			mu[prime[j]*i]=-mu[i];

		}

	}

}

int Judge(int x)

{

	int i,re=0;

	for(i=1;i*i<=x;i++)

		re+=x/(i*i)*mu[i];

	return re;

}

int Bisection(int k)

{

	int l=1,r=k<<1;

	while(l+1<r)

	{

		int mid=(l>>1)+(r>>1)+(l&r&1);

		if( Judge(mid)>=k )

			r=mid;

		else

			l=mid;

	}

	if( Judge(l)>=k )

		return l;

	return r;

}

int main()

{

	int T,k;

	Linear_Shaker();

	for(cin>>T;T;T--)

	{

		scanf("%d",&k);

		printf("%d\n",Bisection(k) );

	}

	return 0;

}