zcmimi's blog
avatar
zc
2020-03-12 23:16:00
  • 本文总阅读量
查看原题

点击跳转

题意:求第k个没有完全平方数因子的数

可以发现答案具有单调性,可以二分答案,然后判断[1,n]中满足条件的个数是否为k

这个结果为

1(0个平方因子)的倍数-【4,9,16,25,...】(1个平方因子)的倍数+【36,100,...】(2个平方因子)的倍数...

也就是:

\sum_{i=1}^{i^2\le n} \mu(i)\left \lfloor \frac n{i^2}\right \rfloor

这样的话只需要线性筛到\sqrt{10^9}\le 40000,然后二分查找就可以了

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define il __inline__ __attribute__ ((always_inline))
#define Fur(i,x,y) for(int i(x);i<=y;++i)
il int min(int x,int y){return x<y?x:y;}
const int N=40011;
int mu[N],pri[4300],cnt=0,k,T;
bool f[N];
il bool chk(int n){
    int sqr=sqrt(n);
    long long ans=0;
    for(int l=1,r;l<=sqr;l=r+1){
        r=min((int)sqrt(n/(n/(l*l))),sqr);
        ans+=n/(l*l)*(mu[r]-mu[l-1]);
    }
    return ans>=k;
}
int main(){
    mu[1]=1;
    Fur(i,2,40000){
        if(!f[i])pri[++cnt]=i,mu[i]=-1;
        Fur(j,1,cnt){
            if(pri[j]*i>40000)break;
            f[i*pri[j]]=1;
            if(i%pri[j])mu[i*pri[j]]=-mu[i];
            else break;
        }
    }
    Fur(i,2,40000)mu[i]+=mu[i-1];
    scanf("%d",&T);
    while(T--){
        scanf("%d",&k);
        int l=k,r=k<<1;
        while(l+1<r){
            int m=(l>>1)+(r>>1)+((l&1)^(r&1));
            if(chk(m))r=m;
            else l=m+1;
        }
        printf("%d\n",chk(l)?l:r);
    }
}
LG 4318 完全平方数
comment评论
Search
search