[bzoj 2440] [中山市选2011]完全平方数

求第k个square-free number. T组数据. (1≤k≤10^9, T≤50) 会以怎样一种形式得到答案呢? 二分似乎不错.

考虑求[1,x]中square-free number的数目. 根据容斥原理, 答案=所有数-质数的平方的倍数+2个质数之积的平方的倍数-3个质数之积的平方的倍数+... 发现容斥系数和莫比乌斯函数是一致的.

如果想证一证这个式子......设某数的标准分解形式中恰有k个质因子指数大于1, 则它是0_{k个质数之积的平方的倍数且不是k+1}inf个质数之积的倍数. 它一共被算了这么多次:

参考: 炫酷反演魔术 - 博客 - vfleaking的博客

由于当, , 所以单次询问的时间复杂度为.

注意二分的时候写成m = l+(r-l)/2防止溢出. 尝试用除法取整分段的优化, 但是开根号太慢了......

const int N = 40557;
short mu[N + 1];
 
void sieve()
{
    static bool f[N + 1];
    static int prime[N/6];
    int cnt = 0;
    mu[1] = 1;
    For (i, 2, N) {
        if (!f[i]) {
            prime[cnt++] = i;
            mu[i] = -1;
        }
        for (int j = 0, t; j < cnt && (t = prime[j] * i) <= N; ++j) {
            f[t] = true;
            if (i % prime[j]) mu[t] = -mu[i];
            else break;
        }
    }
}
 
inline int cal(int x)
{
    int ans = 0;
    for (int i = 1, t; (t = i*i) <= x; ++i)
        ans += x/t*mu[i];
    return ans;
}
 
int main()
{
    sieve();
    int T;
    scanf("%d", &T);
    while (T--) {
        int k;
        scanf("%d", &k);
        int l = 0, r = 1644934081; // (l, r]
        while (r-l > 1) {
            int m = l+(r-l)/2;
            if (cal(m) < k) l = m;
            else r = m;
        }
        printf("%d\n", r);
    }
     
    return 0;
}