bzoj2440 完全平方數

bzoj2440 完全平方數

Description

小 X 自幼就很喜歡數。但奇怪的是，他十分討厭完全平方數。他覺得這些
數看起來很令人難受。由此，他也討厭所有是完全平方數的正整數倍的數。然而
這絲毫不影響他對其他數的熱愛。
這天是小X的生日，小 W 想送一個數給他作為生日禮物。當然他不能送一
個小X討厭的數。他列出了所有小X不討厭的數，然後選取了第 K個數送給了
小X。小X很開心地收下了。
然而現在小 W 卻記不起送給小X的是哪個數了。你能幫他一下嗎？

Input

包含多組測試數據。文件第一行有一個整數 T，表示測試
數據的組數。
第2 至第T+1 行每行有一個整數Ki，描述一組數據，含義如題目中所描述。

Output

含T 行，分別對每組數據作出回答。第 i 行輸出相應的
第Ki 個不是完全平方數的正整數倍的數。

Sample Input

Sample Output

HINT

對於 100%的數據有 1 ≤ Ki ≤ 10^9

, T ≤ 50

莫比烏斯函數的應用

直接求比較困難，我們可以考慮二分答案，問題轉化為[1,x]之間有多少個無平方因子的數。

根據神奇的容斥原理，對於sqrt(x)之內的所有數i有ans=∑((x/(i^2))*mu[i])。其中mu[i]為莫比烏斯函數。(證明請腦補)

然後線性篩求莫比烏斯函數。

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 50005
int t,k,cnt;
int mu[maxn],p[maxn];
bool vst[maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline ll calc(int x)
{
	ll ans=0;
	int tmp=sqrt(x);
	F(i,1,tmp) ans+=x/(i*i)*mu[i];
	return ans;
}
int main()
{
	mu[1]=1;
	F(i,2,50000)
	{
		if (!vst[i]) p[++cnt]=i,mu[i]=-1;
		vst[i]=true;
		for(int j=1;j<=cnt&&p[j]*i<=50000;j++)
		{
			vst[i*p[j]]=true;
			if (i%p[j]==0){mu[i*p[j]]=0;break;}
			else mu[i*p[j]]=-mu[i];
		}
	}
	t=read();
	while (t--)
	{
		k=read();
		ll l=k,r=2000000000,ans;
		while (l<=r)
		{
			ll mid=(l+r)>>1;
			if (calc(mid)>=k) ans=mid,r=mid-1;
			else l=mid+1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}