[数论记录]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)$ ```cpp // 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); } } ```