【洛谷P4318】完全平方数

佚名 6年前 (2019-04-16) 随笔 523人围观抢沙发百度已收录

题目大意：求第 K 个无平方因子数。

题解：第 k 小/大的问题一般采用二分的方式，通过判定从 1 到当前数中满足某一条件的数有多少个来进行对上下边界的转移。
考虑莫比乌斯函数的定义，根据函数值将整数分成了三类，第一类是有平方因子的数，第二类是无平方因子且质因子个数为奇数的数，第三类是无平方因子且质因子个数为偶数的数。我们要求的是\[\sum\limits_{i=1}^n\mu^2(i)\]考虑莫比乌斯函数划分出的三类整数对答案的贡献，发现对于一个数 \(p\) 对答案的贡献为 \((-1)^s\lfloor {n\over p^2}\rfloor\)，观察到每个数的莫比乌斯函数刚好是其对答案贡献的系数，因此可以在 \(O(\sqrt n)\) 时间内进行答案判定，总复杂度为 \(O(\sqrt n logn)\)。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

代码如下

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;

ll k;
int mu[maxn],prime[maxn],tot;
bool vis[maxn];

void seive(){
    mu[1]=1;
    for(int i=2;i<=1e6;i++){
        if(!vis[i])prime[++tot]=i,mu[i]=-1;
        for(int j=1;i*prime[j]<=1e6;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
            mu[i*prime[j]]=-mu[i];
        }
    }
}

ll calc(ll mid){
    ll ret=0;
    for(ll i=1;i*i<=mid;i++)ret+=mu[i]*mid/(i*i);
    return ret;
}

ll solve(){
    ll l=1,r=10*k;
    while(l<r){
        ll mid=l+r>>1;
        if(calc(mid)>=k)r=mid;
        else l=mid+1;
    }
    return l;
}

int main(){
    seive();
    int T;scanf("%d",&T);
    while(T--){
        scanf("%lld",&k);
        printf("%lld\n",solve());
    }
    return 0;
}