SOJ3191Freesquare容斥原理+二分

题目连接：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
#include
#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{
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;
}