P4318 完全平方数 [二分答案+容斥+莫比乌斯函数]

$完全平方数$完全平方数

$Description$Description
小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。

这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了小X。小X很开心地收下了。

然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗？

有 $T$T 组数据, 每组数据的 $K\&lt;=10^9$K<=109, $T\&lt;=50$T<=50 .

$最初想法$最初想法
一个 完全平方数 的倍数分解质因数后, 存在有幂数大于 $1$1的质因子 .
所以一个合法的数字必定是由若干个不同的质数相乘得来的.

思维断点: 怎么算出第 $K$K 个合法的数 ?

$正解部分$正解部分
答案具有 单调性, 考虑 二分答案 ,
要解决的问题为: $[1,x]$[1,x] 内有多少个合法的数,

设在 $[1,x]$[1,x] 有 $Tmp$Tmp 个合法的数,
则 Tmp=x−(22x​+32x​+⋯)+((2∗3)2x​+(3∗5)2x​+⋯)−⋯

设这个式子中的某一项分母为 $t^2$t2, 则 $t\in [1,\sqrt{x}]$t∈[1,x ​], 且 $t$t 是由若干个不同的质数构成的.
根据 莫比乌斯函数 的性质, 没有学过的可以看 这里 ,

• 若 $\mu \left(t\right)=1$μ(t)=1, $t$t是由偶数个质数构成的, 该项为正 .
• 若 $\mu \left(t\right)=-1$μ(t)=−1, $t$t是由奇数个质数构成的, 该项为负 .

于是 $Tmp=\sum _{i=1}^{\sqrt{x}}\mu \left(i\right)\lfloor \frac{x}{i^2}\rfloor$Tmp=i=1∑x ​​μ(i)⌊i2x​⌋
问题得以解决.

时间复杂度 $O\left(\sqrt{x}logx\right)$O(x ​logx), 其中 $x_{max}=10^{10}$xmax​=1010

$实现部分$实现部分
二分的上界为 $K\ast 10$K∗10 (能开多大开多大…) .
但是记得开 $longlong$long long

#include<cmath>
#include<cstdio>
#define reg register
typedef long long ll;

const int maxn = 1e6 + 100;

int p_cnt;
int p[maxn];
int mu[maxn];

bool is_p[maxn];

void sieve(){
        p_cnt = 0, mu[1] = 1;
        for(reg int i = 2; i < maxn; i ++){
                if(!is_p[i]) p[++ p_cnt] = i, mu[i] = -1;
                for(reg int j = 1; j <= p_cnt && p[j]*i < maxn; j ++){
                        int t = p[j] * i;
                        is_p[t] = 1;
                        if(i % p[j] == 0){ mu[t] = 0; break ; }
                        mu[t] = -mu[i];
                }
        }
}

ll Calc(ll mid){
        ll lim = sqrt(mid);
        ll s = 0;
        for(reg ll i = 1; i <= lim; i ++) s += mu[i] * (mid/i/i);
        return s;
}

void Work(){
        ll K;
        scanf("%lld", &K);
        ll l = 1, r = K*10;
        while(l < r){
                ll mid = l+r >> 1;
                if(Calc(mid) >= K) r = mid;
                else l = mid + 1;
        }
        printf("%lld\n", r);
}

int main(){
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
        sieve();
        int T;
        scanf("%d", &T);
        while(T --) Work();
        return 0;
}