[文章目录]
Description
小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。 这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了小X。小X很开心地收下了。然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗？
k<=10^9。显然我们不能线性筛。那么我们考虑二分，对于一个mid，我们找1~mid中有都少个数满足条件，考虑容斥原理。1~n中2x2的倍数有n/(2x2)个。然后3同理。当遇到一个数n的时候，对答案累加的值就是n/()*μ(i)。据说μ(i)也被称作约数的容斥系数。那么，我们快筛mu到10^7，然后每次O(1)查询。时间复杂度：O(Tlogx√x)级别。据测量，x<=17亿。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 10000000
using namespace std;
typedef long long ll;
int mu[10001000],pri[701000],cnt;
bool v[10001000];
void quick_mu()
{
mu[1]=1;
for(int i=2;i<=N;i++)
{
if(!v[i]) pri[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&i*pri[j]<=N;j++)
{
v[i*pri[j]]=1;
if(i%pri[j]==0)
{
mu[i*pri[j]]=0;
break;
}
else mu[i*pri[j]]=mu[i]*-1;
}
}
}
ll get_num(const ll x)
{
ll re=x;
for(ll i=2;i*i<=x;i++)
re+=(x/(i*i))*mu[i];
return re;
}
int main()
{
quick_mu();
ll T,k;
scanf("%lld",&T);
while(T--)
{
scanf("%lld",&k);
ll l=1,r=1700000000ll,mid;
while(l<r)
{
mid=(r&l&1)+(l>>1)+(r>>1);
if(get_num(mid)>=k) r=mid;
else l=mid+1;
}
printf("%lld\n",r);
}
return 0;
}