[数论记录]P4318 完全平方数

挺有意思的一个题。

题目要求我们求第k个不是完全平方数的数。

考虑二分答案转化为判定性问题,我们可以统计某个数前面有几个非平方数。

• 容斥

先是n.

我们可以考虑先减去\sum\limits_{i=2}^{\sqrt{n}}\lfloor n/i^2\rfloor

很明显我们算多了,再减去有两个因子的数的贡献。

又减多了,那么加上有三个因子的数的贡献……

如此就是莫比乌斯函数的体现,答案就是\sum\limits_{i=1}^{\sqrt{n}}\mu(i)\lfloor n/i^2\rfloor

复杂度O(T\sqrt{n}logn)

• 推式子

有时候容斥不那么容易想得到,那么就要推推式子:

• 万U群里的神仙网友指了一条路子:

设f(x)=\sum\limits_{i=1}^n[x^2\text{是}i\text{的最大平方因子}]

F(x)=\sum\limits_{x|d}f(d)=\sum\limits_{i=1}^n[x^2\text{是}i\text{的平方因子}]=\lfloor n/x^2\rfloor

反演一下就是f(1)=\sum\limits_{k=1}^{\sqrt{n}}\mu(k)F(k)=\sum\limits_{k=1}^{\sqrt{n}}\mu(k)\lfloor n/k^2\rfloor

• 万U群里的神仙网友指了又一条路子:

设f(x)=\sqrt{i\text{的最大平方因子}}

我们要求的就是\sum\limits_{i=1}^n[f(i)=1]=\sum\limits_{i=1}^n\sum\limits_{d|f(i)}\mu(d)

又因为d|f(i)\leftrightarrow d^2|i

=\sum\limits_{i=1}^n\sum\limits_{d^2|i}\mu(d)=\sum\limits_{d=1}^{\sqrt{n}}\mu(d)\sum\limits_{d^2|i}1=\sum\limits_{k=1}^{\sqrt{n}}\mu(d)\lfloor n/d^2\rfloor

由此也得到一个有趣的结论:\mu^2(i)=\sum\limits_{d^2|i}\mu(d)

// luogu-judger-enable-o2
#include<algorithm>
#include<cstdio>
#define MaxN 45678
using namespace std;
int T;
int tn,p[MaxN],mu[MaxN];
bool e[MaxN];
void getsth(int lim)
{
  mu[1]=1;e[1]=1;
  for (int i=2;i<=lim;i++){
    if (!e[i]){
      p[++tn]=i;
      mu[i]=-1;
    }
    for (int j=1;j<=tn&&i*p[j]<=lim;j++){
      e[i*p[j]]=1;
      if (i%p[j]==0)break;
      mu[i*p[j]]=-mu[i];
    }
  }
}
long long calc(long long n)
{
  long long ans=0;
  for (int i=1;1ll*i*i<=n;i++)
    ans+=mu[i]*(n/(1ll*i*i));
  return ans;
}
int main()
{
  getsth(45000);
  scanf("%d",&T);
  while(T--){
    long long l=1,r,mid,k;
    scanf("%lld",&k);r=k+k+100;
    while(l<r){
      mid=(l+r)>>1;
      if (calc(mid)>=k)r=mid;
      else l=mid+1;
    }printf("%lld\n",r);
  }
}