BZOJ-2986: Non-Squarefree Numbers

Description

一个正整数K被称为squarefree,如果它没有一个D^2(D>1)这样的约数。找出第N个不是squarefree的数。1<=N<=10^10

求一个数x，使得
这个东西等价于把2^2的倍数个数加起来，再加上3^2的倍数个数加起来，再减去6^2的倍数个数。即，发现只需要预处理10^5的，然后根号时间就能求出来了。具有单调性，二分即可

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int mu[300000],pri[300000],cnt;
bool v[300000];
ll n;
void quick_mu()
{
    mu[1]=1;
    for(int i=2;i<=300000;++i)
    {
        if(!v[i]) pri[++cnt]=i,mu[i]=1;
        for(int j=1;i*pri[j]<=300000&&j<=cnt;++j)
        {
            v[i*pri[j]]=1;
            if(i%pri[j]==0) {mu[i*pri[j]]=0; break;}
            mu[i*pri[j]]=-mu[i];
        }
    }
}
ll check(ll x)
{
    ll re=0;
    for(ll i=2;i*i<=x;++i)
        re+=(x/(i*i))*mu[i];
    return re;
}
int main()
{
    quick_mu();
    scanf("%lld",&n);
    ll l=4,r=30000000000ll,mid;
    while(l<r)
    {
        mid=l+r>>1;
        if(check(mid)>=n) r=mid;
        else l=mid+1;
    }
    printf("%lld",r);
    return 0;
}