LINK：[2440中山市选2011 完全平方数]
这个中山市太强了 还有市选。。
之所以做这道题是因为这道题 有一个朋友给我的题目 我没想出来 和这道题类似。注意 活用容斥！
楔子：求出1~n内所有不含平方质因数的数字个数。(nleq 10^{12})
更形象一点(sum_{i=1}^{n}mu(i)^2) 对这个东西求和。
想了一会杜教筛 发现搞不了 没有什么积性函数能卷这个东西得到一个比较好的积性函数。
min25？我也不会我也不懂。。。
考虑容斥 我们还是利用质因数来筛 首先被筛掉的是 n/p*p 这说明了(pleq 10^6).
发现这样筛下去即可 容斥系数使用(mu)即可。
那现在可以考虑这道题了 第k个数。
求第k大 直接上二分。考虑如何check 直接暴力容斥出mid之内有多少个数字是非完全平方的即可。
总复杂度 Tlogksqrt(k) .
const ll MAXN=1000010;
ll T,n,maxx,top;
ll p[MAXN],v[MAXN],mu[MAXN];
inline void prepare()
{
mu[1]=1;
rep(2,maxx,i)
{
if(!v[i])
{
p[++top]=v[i]=i;
mu[i]=-1;
}
rep(1,top,j)
{
if(maxx/i<p[j])break;
v[i*p[j]]=p[j];
if(v[i]==p[j])break;
mu[i*p[j]]=-mu[i];
}
}
}
inline ll calc(ll n)
{
ll ans=0;
for(ll i=1;i*i<=n;++i)ans+=mu[i]*n/(i*i);
return ans;
}
int main()
{
freopen("1.in","r",stdin);
get(T);maxx=1000010;
prepare();
//printf("%lld
",calc(10000000000ll));
while(T--)
{
get(n);
ll l=1,r=10000000000ll;
while(l<r)
{
ll mid=(l+r)>>1;
if(calc(mid)>=n)r=mid;
else l=mid+1;
}
printf("%lld
",r);
}
return 0;
}
二分上界可以自己算一下。