P4318 完全平方数

题目描述

求第 k 个，不是完全平方数也不是完全平方数倍数的数。

Solution

将数 x 分解质因子，设
x=p_1^{a_1}p_2^{a_2}\dots p_n^{a_n}
如果 x 不是完全平方数也不是完全平方数的倍数，那么必有 \forall a \leq 1

那么对于这样的数，有 \mu(x)^2=1

所以我们就要找到最小的 n 使得
\sum_{i=1}^n\mu^2(i) =k
但是这样很难做，我们考虑容斥

x=p_1p_2\dots p_n ，\forall p>1

如果 n 是奇数，那么它会给 \forall y,x^2|y 带来一个正贡献

如果 n 是偶数，那么它会给 \forall y,x^2|y 带来一个负贡献

那么这个正负刚好是 \mu(x)

所以我们就要求min(n)
\sum_{i=1}^n \mu(i)*\lfloor\frac{n}{i^2}\rfloor=k

#include<bits/stdc++.h>
#define ll long long 
const int N = 1e5+10;
bool vis[N];
int prime[N];
int Mob[N];
int g[N],pre[N];
int k;
void Mobius_sieve(){
     int cnt = 0;
     vis[1] = 1;
     Mob[1] = 1;
     for(int i = 2; i < N; i++){
        if(!vis[i])
            prime[cnt++] = i, Mob[i] = - 1 , g[i] = 1;
        for(int j = 0; j < cnt && 1LL * prime[j] * i < N; j++){
            vis[prime[j] * i] = 1;
            g[prime[j]*i] = g[i] + 1;
            Mob[i * prime[j]] = (i % prime[j] ? -Mob[i]: 0);
            if(i % prime[j] == 0)
                break;
        }
    }
    for(int i=1;i<N;++i)    
        pre[i]=pre[i-1]+Mob[i];
}
int check(ll x){
    ll ans = 0 ;
    for(ll i=1;i*i<=x;++i)
        ans += 1ll*Mob[i]*(x/(i*i));    
    return ans>=k;
}
int main(){
    Mobius_sieve();
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&k);
        ll l = 1e10 , r = 0;
        while(l-1>r){
            ll mid=l+r>>1;
            if(check(mid))
                l=mid;
            else
                r=mid;
        }
        printf("%lld\n",l);
    }
}