Bzoj 2440 完全平方数

题解

question

求第 $k$ 个无平方因子数，分解之后所有质因数的次数都为1的数

slove

二分答案，问题转化为 $[1, mid]$ 中无平方因子数个数
判断：对于 $\sqrt(mid)$ 以内的所有质数，$mid$ 以内的无平方因子数为
=0个质数乘积的平方的倍数的数的数量(1的倍数)
-每个质数的平方的倍数的数的数量(9的倍数,25的倍数, $\dots$ )
+每2个质数乘积的平方的倍数的数的数量(36的倍数,100的倍数, $\dots$ )
-$\dots$
发现每个数字 $i$ 前的符号为 $\mu(i)$
then，check时只需判断 $Q(x) = \sum_{i=1}^{\lfloor \sqrt(x) \rfloor} \mu(i) \lfloor \frac{x}{i^2} \rfloor$ 与 $mid$ 的大小即可
当然要首先筛出 $\mu()$

与反演无关，是莫比乌斯函数的一个应用

Code

二分有个什么wobuzhidao的错误
发现比样例少 $1$, $+1$ 竟然过了，woc，why

#include <bits/stdc++.h>
#define LL long long
const int N = 1e5 + 10;
LL T, n, miu[N], prime[N], bo[N];
void Make_miu() {
    miu[1] = 1;
    for(int i = 2; i < N; i ++) {
        if(!bo[i]) {prime[++ prime[0]] = i; miu[i] = -1;} // 1个质因子 
        for(int j = 1; j <= prime[0] && prime[j] * i < N; j ++) {
            bo[i * prime[j]] = 1; // 非素数 
            if(i % prime[j] == 0) {
                miu[i * prime[j]] = 0; // 有 prime[j] * prime[j] 
                break;
            } else { // 与 i 质因子的个数奇偶性相反 
                miu[i * prime[j]] = - miu[i];
            }
        }
    } 
}
bool See(LL x, LL t) {
    LL ret(0);
    for(LL i = 1; i * i <= x; i ++) ret += (miu[i] * (x / (i * i)));
    return ret < t;
}
LL Get_Ans(LL x) {
    LL L = 0, R = x * 2, Ans;
    while(L <= R) {
        LL Mid = (L + R) >> 1;
        if(See(Mid, x)) L = Mid + 1, Ans = Mid;
        else R = Mid - 1;
    }
    return Ans;
} 
int main() {
    std:: cin >> T;
    Make_miu();
    for(; T --; ) {
        std:: cin >> n;
        std:: cout << Get_Ans(n) + 1 << "\n"; 
    }
    return 0;
}