\(Luogu4318\)
题目大意:多组数据求第\(k\)个没有完全平方因子的数是谁。
那么可以设\(f(i)\)为只是\(i^2\)倍数的数的个数。
那要求\(n\)以内的不是完全平方数倍数的数的个数，那就要把是倍数的累加起来，减去。
设\(F(i)=\sum_{i|d}f(d)\)
则\(F\)函数表示的即为上面所述的意思。
考虑\(f(i)\)等于什么。
显然是\(\frac{n}{i^2}\)对吧，就是求\(n\)是\(i^2\)的多少倍就行。
那么考虑\(F(i):\)
\[F(i)=\sum_{i|d}f(d)=\sum_{i|d}\frac{n}{d^2}\]
可以看出来就是一个倍数形式的莫比乌斯反演。反演得：
\[f(i)=\sum_{i|d}\mu(\frac{d}{i})F(d)\]
那么对于一个数它前面有多少完全平方数的倍数，就等于当前的\(f(1)\)吧，仅仅是\(1^2=1\)的数的倍数而不是其它完全平方数的倍数的数的个数。
那么由上面公式有：
\[f(1)=\sum_{d}\mu(d)F(d)=\sum_{d}^{d*d<=n}\mu(d)\frac{n}{d^2}\]
这个式子可以数论分块对吧，求这个东西的复杂度是\(O(\sqrt{n})\)
那么考虑求一个序列里面第\(k\)大的求法。（不能排序）
看到\(k\)的范围想到二分。
发现循环范围小于等于\(\sqrt{n}\)，于是线性筛出\(\sqrt{MAX}\)的\(\mu(i)\)，预处理前缀和，解决的时候套一个二分板子即可。
总复杂度\(O(T\sqrt{n}\log{n})\)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
#define int long long
const int MAXN=5e4+10;
int fg[MAXN+10],mu[MAXN+10],T,k;
int prime[MAXN+10],tot,sum[MAXN+10];
void screen(){
mu[1]=1;
for(int i=2;i<=MAXN;++i){
if(!fg[i])prime[++tot]=i,mu[i]=-1;
for(int j=1;j<=tot&&i*prime[j]<=MAXN;++j){
fg[i*prime[j]]=1;
if(i%prime[j]==0){
mu[i*prime[j]]=0;
break;
}
mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<=MAXN;++i)sum[i]=sum[i-1]+mu[i];
}
bool check(int x){
int ans=0,m=sqrt(x);
for(int l=1,r;l<=m;l=r+1){
r=min((int)sqrt(x/(x/(l*l))),m);
ans+=(sum[r]-sum[l-1])*(x/(l*l));
}
return ans>=k;
}
void solve(){
int l=1,r=2000000000;
while(l+1<r){
int mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid;
}
if(check(l))printf("%lld\n",l);
else printf("%lld\n",r);
}
signed main(){
scanf("%lld",&T);
screen();
while(T--){
scanf("%lld",&k);
solve();
}
return 0;
}注意二分范围不能太小。