Description
小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。
这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一个小 X 讨厌的数。他列出了所有小 X 不讨厌的数，然后选取了第 K 个数送给了小 X 。小 X 很开心地收下了。
然而现在小 W 却记不起送给小 X 的是哪个数了。你能帮他一下吗？
包含多组测试数据。文件第一行有一个整数 T，表示测试数据的组数。
第 2 至第 T+1 行每行有一个整数 Ki ，描述一组数据，含义如题目中所描述。
Output
含 T 行，分别对每组数据作出回答。第 i 行输出相应的第 Ki 个不是完全平方数的正整数倍的数。
4
1
13
100
1234567
Sample Output
1
19
163
2030745
思路
题目其实是在求第 k 个无平方因子数的数值（分解之后质因子次数都为 1 的数）。
首先我们将问题转化为求区间 [1,x] 之间有多少个无平方因子数，然后二分得出答案。
根据容斥原理我们知道，对于
x√
以内的所有质数
x 以内的无平方因子数 = 无需是任何质数倍数的数的个数（即 x ） - 是至少一个质数平方倍数的数的数量 + 是至少两个质数平方倍数的数的数量 - …
AC 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn =
51000;
typedef long long LL;
int mu[maxn],prime[maxn];
bool check[maxn];
LL n;
void Moblus()
{
memset(check,
false,
sizeof(check));
mu[
1]=
1;
int tot=
0;
for(
int i=
2; i<maxn; i++)
{
if(!check[i])
{
prime[tot++]=i;
mu[i]=-
1;
}
for(
int j=
0; j<tot && i*prime[j]<maxn; j++)
{
int num=i*prime[j];
check[num]=
true;
if(i%prime[j]==
0)
{
mu[num]=
0;
break;
}
else
mu[num]=-mu[i];
}
}
}
LL judge(LL x)
{
LL ans=
0;
for(LL i=
1; i*i<=x; i++)
ans+=x/(i*i)*mu[i];
return ans;
}
void solve()
{
LL low=
0,high=n<<
1,ans;
while(low<=high)
{
LL mid=(low+high)/
2;
LL cnt=judge(mid);
if(cnt<n)
low=mid+
1;
else if(cnt>=n)
ans=mid,high=mid-
1;
}
cout<<ans<<endl;
}
int main()
{
Moblus();
int T;
cin>>T;
while(T--)
{
cin>>n;
solve();
}
return 0;
}
