bzoj2440: [中山市选2011]完全平方数

莫比乌斯反演

---

题目链接

bzoj2440: [中山市选2011]完全平方数

题解

大意：求第$k$个无平方因子数。

无平方因子数(Square-Free Number)，即分解之后所有质因数的次数都为1的数

联想莫比乌斯函数，若$n$是答案，那么有

$$k=n-\sum_{i=1}^n(1-|\mu(i)|)$$
考虑二分$n$，check$[1,n]$中有多少个无平方因子数。
根据容斥，枚举$[1,\sqrt{n}]$中的质数(容斥带有 质数平方因子的数的个数)，答案为

$[1,n]$中，可用0个质数平方倍数表示的个数-(可用)1个质数平方倍数表示的个数+（可用）2个质数平方倍数表示的个数....
$也就是n - \frac{(-1)^kmid}{p1*p2*...*pk}$

那么显然，对于容斥系数可以用莫比乌斯函数$\mu(i)$表示
那么答案也就是

$$\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}\mu(i)*\lfloor\frac{n}{i^2}\rfloor$$
另外,二分mid时会炸int

代码

// luogu-judger-enable-o2
#include<cmath> 
#include<cstdio> 
#include<algorithm> 
const int maxn = 200007;
#define int long long
inline int read() { 
    int x = 0; 
    char c = getchar(); 
    while(c < '0' || c > '9') c = getchar(); 
    while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar(); 
    return x; 
} 
int prime[maxn],mu[maxn];bool p[maxn]; 
void get_mu() { 
    mu[1] = 1; 
    int n = maxn - 7,num = 0; 
    for(int i = 2;i <= n;++ i) {
        if(!p[i]) prime[++num] = i,mu[i] = -1;
        for(int j = 1;j <= num && prime[j] * i <= n;++ j) { 
            p[i * prime[j]] = 1; 
            if(i % prime[j] == 0) break; 
            mu[i * prime[j]] = -mu[i]; 
        } 
    } 
} 
int check(int x) { 
    int ret = 0 ;
    for(int i = 1;i <= sqrt(x); ++ i ) {
        ret += mu[i] * (x / (i * i)); 
    } 
    return ret; 
} 
main() { 
    get_mu();
    int T = read(); 
        for(int k;T --;) { 
        k = read(); 
        int l = 1,r = 2000000000,ans;  
    //  if(k == 1)puts("1"); 
        while(l <= r) { 
            int mid = l + r >> 1; 
            if(check(mid) >= k) ans = mid,r = mid - 1; 
            else l = mid + 1; 
        } 
        printf("%lld\n",ans); 
    }   
    return 0; 
}