深圳专业网站设计公司哪家好/seo网站外链平台

(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(Tsqrt{n}log{n}))

#include

#include

#include

#include

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

int mid=(l+r)>>1;

if(check(mid))r=mid;

else l=mid;

}

if(check(l))printf("%lld

",l);

else printf("%lld

",r);

}

signed main(){

scanf("%lld",&T);

screen();

while(T--){

scanf("%lld",&k);

solve();

}

return 0;

}

注意二分范围不能太小。