题目链接

题解

发现答案满足可二分性，考虑二分答案，假设值为$x$，容斥之后发现$[1,x]$中不是完全平方数的个数就是

∑i=1xμ(i)⌊xi2⌋ \sum_{i=1}^{\sqrt{x}} \mu(i)\lfloor\frac{x}{i^2}\rfloor i=1∑x​​μ(i)⌊i2x​⌋

代码

#include 
    
     int read(){
      int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {
          if(ch=='-')        {
              f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {
          x=x*10+ch-'0';      ch=getchar();    }  return x*f;}const int maxn=100000;int p[maxn+10],prime[maxn+10],cnt,mu[maxn+10];int getprime(){
      p[1]=mu[1]=1;  for(int i=2; i<=maxn; ++i)    {
          if(!p[i])        {
              prime[++cnt]=i;          mu[i]=-1;        }      for(int j=1; (j<=cnt)&&(i*prime[j]<=maxn); ++j)        {
              int x=i*prime[j];          p[x]=1;          if(i%prime[j]==0)            {
                  mu[x]=0;              break;            }          mu[x]=-mu[i];        }    }  return 0;}int T,n;int check(int x){
      int ans=0;  for(int i=1; i*i<=x; ++i)    {
          ans+=mu[i]*(x/(i*i));    }  return ans;}int main(){
      getprime();  T=read();  while(T--)    {
          n=read();      int l=n,r=n*2;      while(l<=r)        {
              int mid=(1ll*l+r)>>1;          if(check(mid)>=n)            {
                  r=mid-1;            }          else            {
                  l=mid+1;            }        }      printf("%d\n",r+1);    }  return 0;}