题意

求第 k 个不是完全平方数（除 1 以外）的正倍数的数。

分析

利用二分法求解，二分 x ，判断 x 是否是第 k 个数即可，那么我们就要计算 [1, x] 有几个符合条件的数。

首先本题用到容斥原理的思想，

sum = 1 的倍数的数的个数 - (4, 8, 9, ) 这些质因子个数为 1 的平方的倍数的数的个数 + (36, ) 这些质因子个数为 2 的平方的倍数的数的个数 ...

而根据莫比乌斯函数 \(\mu(n)\) 的定义：

设 \(n = p_1 ^ {k_1} \cdot p_2 ^ {k_2} \cdot\cdots\cdot p_m ^ {k_m}\) ，其中 p 为素数，则定义如下：

\(\mu(n) = \begin{cases} 1 & n = 1 \\ (-1) ^ m & \prod\limits_{i = 1} ^ {m} k_i = 1 \\ 0 & \textrm{otherwise}(k_i \gt 1) \end{cases}\)

最终得到下面的式子：

\(sum = \sum_{i=1}^{\left \lfloor \sqrt{x} \right \rfloor}\mu(i)\left \lfloor \frac{x}{i^{2}}\right \rfloor\)

我们可以通过线性筛来求出莫比乌斯函数的值。

code

#include
    
     using namespace std;typedef long long ll;const int MAXN = 1e6 + 10;int not_prime[MAXN];int prime[MAXN];int mu[MAXN];void getMu() {    mu[1] = 1;    int cnt = 0;    for(int i = 2; i < MAXN; i++) {        if(!not_prime[i]) {            prime[cnt++] = i;            mu[i] = -1;        }        for(int j = 0; i * prime[j] < MAXN; j++) {            not_prime[i * prime[j]] = 1;            if(i % prime[j] == 0) {                mu[i * prime[j]] = 0;                break;            }            mu[i * prime[j]] = -mu[i];        }    }}ll cal(ll x) {    ll s = 0;    for(ll i = 1; i * i <= x; i++) {        s += mu[i] * (ll)(x / (i * i));    }    return s;}int main() {    getMu();    int T;    cin >> T;    while(T--) {        ll k;        cin >> k;        ll l = 1, r = 1e10, mid = (l + r) / 2;        while(l < r) {            if(cal(mid) >= k) r = mid;            else l = mid + 1;            mid = (l + r) / 2;        }        cout << mid << endl;    }    return 0;}