首先根据样例或者自己打表大概可以知道,对于询问k,答案不会超过k<<1,那么我们就可以二分答案,求当前二分的值内有多少个数不是完全平方数的倍数,这样就可以了,对于每个二分到的值x,其中完全平方数的倍数的个数为Σmiu(i)*(n/(i*i)),原理就是容斥,但是根据莫比乌斯反演应该也是能推出来的(我没推出来)。

  反思:开始莫比乌斯函数筛错了,后来的时候没用longlong,导致二分的时候int溢出了,这样就死循环了,找了半天错。

/**************************************************************
Problem: 2440
User: BLADEVIL
Language: C++
Result: Accepted
Time:1164 ms
Memory:2456 kb
****************************************************************/ //By BLADEVIL
#include <cstdio>
#include <iostream>
#include <cmath>
#define maxn 50010 using namespace std; long long mindiv[maxn],prim[maxn],miu[maxn]; void prepare()
{
miu[]=;
for (long long i=;i<=;i++)
{
if (!mindiv[i])
{
prim[++prim[]]=i;
miu[i]=-;
}
for (long long j=;j<=prim[]&&prim[j]*i<=;j++)
{
mindiv[i*prim[j]]=prim[j];
if (!(i%prim[j]))
{
miu[i*prim[j]]=;
break;
}
miu[i*prim[j]]=-miu[i];
}
}
} long long calc(long long x)
{
long long tot=,t;
for (long long i=;i<=sqrt(x);i=t+)
{
t=x/(x/(i*i)); t=sqrt(t);
//printf("%d %d\n",i,t);
tot+=(miu[t]-miu[i-])*(x/(i*i));
//printf("%d\n",tot);
//printf("%d %d\n",miu[t],miu[i-1]);
}
return tot;
} int main()
{
prepare();
for (long long i=;i<=;i++) miu[i]+=miu[i-];
//printf("%d",calc(1));
//for (long long i=1;i<=100;i++) printf("%d ",miu[i]);
long long task;
scanf("%lld",&task);
while (task--)
{
long long l=1ll,r,n,ans;
scanf("%lld",&n);
r=n<<;
while (l<=r)
{
long long mid=(l+r)>>;
//printf("%d %d %d\n",l,r,mid);
if (calc(mid)>=n)
{
ans=mid;
r=mid-1ll;
} else l=mid+1ll;
//printf("%d %d %d\n",l,r,mid);
}
printf("%lld\n",ans);
}
return ;
}
05-13 01:44