BZOJ2440【中山市选2011】完全平方数 <二分+莫比乌斯容斥>

Problem

【中山市选2011】完全平方数

Description

小自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。
这天是小的生日，小想送一个数给他作为生日礼物。当然他不能送一个小讨厌的数。他列出了所有小不讨厌的数，然后选取了第个数送给了小。小很开心地收下了。
然而现在小却记不起送给小的是哪个数了。你能帮他一下吗？

Input

包含多组测试数据。文件第一行有一个整数，表示测试数据的组数。
第至第行每行有一个整数，描述一组数据，含义如题目中所描述。

Output

含行，分别对每组数据作出回答。第行输出相应的第个不是完全平方数的正整数倍的数。

Sample Input

Sample Output

HINT

对于的数据有

标签：二分答案 莫比乌斯容斥

Solution

没做起水题…

似乎答案不超过？不会证。

二分答案，对于当前尝试的答案，统计以下有多少个符合条件的数。

容易发现为了避免算重复，可以约数容斥来算。另外，如果完全平方数的底数有平方因子，一定不会产生贡献。
设所有质数的集合为，所有由两个不同质数相乘而得数的集合为，…，由个不同质数相乘而得的数的集合为，那么符合条件的数的个数为：

发现上面的式子可以用莫比乌斯函数简化，即

这样每次用时间，总复杂度为。

Code

#include <bits/stdc++.h>
#define MAX_N 50000
#define mid (l+((r-l)>>1))
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
bool NotPri[MAX_N+5];
int pri[MAX_N+5], mu[MAX_N+5], cnt;
void init() {
    mu[1] = 1;
    for (int i = 2; i <= MAX_N; i++) {
        if (!NotPri[i]) pri[cnt++] = i, mu[i] = -1;
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > MAX_N) break;
            NotPri[i*pri[j]] = true;
            if (i%pri[j]) mu[i*pri[j]] = -mu[i];
            else {mu[i*pri[j]] = 0; break;}
        }
    }
}
bool chk(int n, int k) {
    int rk = 0;
    for (int i = (int)sqrt(n); i; i--)
        rk += mu[i]*(n/i/i);
    return rk >= k;
}
void sol(int k) {
    int l = 1, r = 2*k, ans = -1;
    while (l <= r)
        if (!chk(mid, k)) l = mid+1;
        else ans = mid, r = mid-1;
    printf("%d\n", ans);
}
int main() {
    int T, k;	read(T), init();
    while (T--) read(k), sol(k);
    return 0;
}