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

链接

https://www.lydsy.com/JudgeOnline/problem.php?id=2440

题解

二分，转化为判定1到x内的无平方因子的数的个数
(范围自己二分着试)
然后容斥
含0个平方因子-含1个平方因子+含有两个平方因子~~~~
于是观察一下上面那个式子，再联想mobius函数的定义，就会发现(?)容斥中的系数就是mobius函数。
别问我，我是懵逼的
update cpp :2019.5.3

代码

 
#include <bits/stdc++.h>
#define int long long
const int N = 1e6+7;
using namespace std;
int read() {
    int x = 0, f = 1; char s = getchar();
    for (;s > '9' || s < '0'; s = getchar()) if (s == '-') f = -1;
    for (;s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';
    return x * f;
}
int k;
int pri[N], vis[N], tot, mu[N], g[N];
void Euler(int limit) {
    mu[1] = 1;
    for (int i = 2; i <= limit; ++i) {
        if (!vis[i]) {
            pri[++tot] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= tot && i * pri[j] <= limit; ++j) {
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                mu[i * pri[j]] = 0;
                break;
            }
            mu[i * pri[j]] = -mu[i];
        }
    }
}
bool check(int mid) {
    int ans = 0;
    for (int i = 1; i * i <= mid; ++i)
        ans += mu[i] * (mid / (i * i));
    return ans >= k;
}
void solve() {
    k = read();
    int l = 0, r = 1700000000, ans = 0;
    while (l <= r) {
        int mid = (1LL*l + 1LL*r) >> 1;
        if (check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    printf("%lld\n", ans);
}
signed main() {
    Euler(1000000);
    int T = read();
    while (T--) solve();
    return 0;
}