BZOJ 2440 [中山市选2011]完全平方数

题目大意

求第N个不是完全平方数的正整数倍的数。

首先直接求不是完全平方数的第N个数有点困难= =

转化成求完全平方数吧……也不是很会= =

所以考虑二分，问题就转化成求X之前有多少非完全平方数。

之后可以转化成求有多少完全平方数。

所以考虑容斥，答案就是X-一个数的平方的倍数个数+两个数的平方的倍数个数......

发现$\mu(N)$正好可以作为容斥用的常数。

之后就过了= =

#include <cstdio>
#define R register
int n,prm[50001];
short mu[50001];
bool v[50001];
inline void init()
{
	R int cnt=0;
	mu[1]=1;
	for(R int i=2;i<=50000;++i)
	{
		if(!v[i]) prm[++cnt]=i,mu[i]=-1;
		for(R int j=1;j<=cnt&&i*prm[j]<=50000;++j)
		{
			v[i*prm[j]]=true;
			if(i%prm[j]) mu[i*prm[j]]=-mu[i];
			else break;
		}
	}
}
inline bool check(long long tg)
{
	R long long ret=0;
	for(R long long i=1;i*i<=tg;++i) ret+=(tg/(i*i))*mu[i];
	return ret<n;
}
int main()
{
	init();
	R int T;
	R long long l,r,mid;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		l=0,r=2000000000ll;
		while(l<r)
		{
			mid=(l+r)>>1;
			if(check(mid)) l=mid+1;
			else r=mid;
		}
		printf("%lld\n",l);
	}
	return 0;
}