题目连接：http://zuojie.3322.org:88/soj/problem.action?id=3191
Description
A positive integer is said to be squarefree if it is divisible by no perfect square larger than 1. For example, the first few squarefree numbers are {1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, ...}. Can you tell me the K-th ( 1-indexed ) smallest squarefree number.
Input
The first line of the input will be a integer to represent the number of test cases.For each test case there is only one line contains only one integer K. ( 1 <= K <= 10^9 )There is a blank line before each test case.
Output
For each test case output the answer on a single line:The K-th smallest squarefree number.
Sample Input
6
1
2
7
1000
1234567
1000000000
Sample Output
1
2
10
1637
2030745
1644934081
用360浏览器看代码可能看到的是乱码，建议使用搜狗浏览器，邪恶的CSDN，改版后让我非常窝火。。
好了，扯远了，我讲一下这个题的思路吧。这个题也是传说中的windy教主出的。。非常霸气的一道题目。我刚开始做的时候大体思路还是正确的，就是二分+容斥。
可是大量的细节和模拟能力不足导致迟迟不能AC。后来参考了下别人的思路和代码，自己理解后再次敲了下，轻松AC了。
我们可以预先处理出250以下的素数，然后通过这一些素数我们选出2-50000以内符合要求的数。并且判断每一个数的质因数个数是奇数还是偶数（以后用来容斥）
最后是利用二分答案来实现的。
详见代码：
#include<stdio.h>
#include<string.h>
#define MAXN 50000
typedef long long LL;
LL a[MAXN];
LL prime[250];
bool flag[250];
void init()
{
LL i,j,num=0,k;
for(i=2;i<250;i++)
{
if(!flag[i])
{
prime[num++]=i;
for(j=i*i;j<250;j=j+i)
flag[j]=true;
}
}
for(i=2;i<MAXN;i++)
{
a[i]=1;
k=i;
for(j=0;prime[j]*prime[j]<=k;j++)
{
if(k%prime[j]==0)
{
a[i]=-a[i];
k=k/prime[j];
if(k%prime[j]==0)
{
a[i]=0;
break;
}
}
}
if(k>1&&a[i]!=0)
a[i]=-a[i];
}
}
void solve(LL n)
{
LL left,right,mid,ans,i;
left=1,right=1644934081;
while(left<=right)
{
mid=(left+right)/2;
ans=mid;
for(i=2;i*i<=mid;i++)
ans=ans+(mid/(i*i))*a[i];
if(ans>=n)
right=mid-1;
else
left=mid+1;
}
printf("%lld\n",left);
}
int main()
{
LL t,n;
init();
while(scanf("%lld",&t)!=EOF)
{
while(t--)
{
scanf("%lld",&n);
solve(n);
}
}
return 0;
}