BZOJ 2440 [中山市选2011]完全平方数 （容斥）

Description

小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。

这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一个小 X 讨厌的数。他列出了所有小 X 不讨厌的数，然后选取了第 K 个数送给了小 X 。小 X 很开心地收下了。

然而现在小 W 却记不起送给小 X 的是哪个数了。你能帮他一下吗？

Input

包含多组测试数据。文件第一行有一个整数 T，表示测试数据的组数。

第 2 至第 T+1 行每行有一个整数 Ki ，描述一组数据，含义如题目中所描述。

Output

含 T 行，分别对每组数据作出回答。第 i 行输出相应的第 Ki 个不是完全平方数的正整数倍的数。

Sample Input

4
1
13
100
1234567

Sample Output

1
19
163
2030745

思路

题目其实是在求第 k 个无平方因子数的数值（分解之后质因子次数都为 1 的数）。

首先我们将问题转化为求区间 [1,x] 之间有多少个无平方因子数，然后二分得出答案。

根据容斥原理我们知道，对于 $\sqrt{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;
}