Description：

求第 $k$ 大无平方因子的数。

$1\le K_i \le 10^9$

Solution：

直接求很不好求，考虑二分一个答案 $mid$ ，判断前 $mid$ 个数中是否有 $k$ 个数满足要求。

不难想到容斥，问题变为 $n-只有一个质因子的数的平方的倍数的个数+ 只有两个质因子的数的平方的倍数的个数 - 只有三个质因子的数的平方的倍数的个数$

可以用 $dfs$ 容斥做，但是由于莫比乌斯函数就是容斥系数，可以枚举所有小于等于 $\sqrt{n}$ 的数，如果这个数有奇数个质因子，那么容斥时应减掉，莫比乌斯函数为 $-1$ ，偶数个质因子容斥时应加上，莫比乌斯函数为 $1$ ，于是计算式为 $\begin{align}\sum_{i=1}^{\sqrt {mid}}\mu(i)\times \frac {mid}{i^2}\end{align}$

二分的范围为 $[k,2\times k]$ ，原因我也不知道。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 50000

bool isprime[MAXN];

typedef long long ll;

ll prime[MAXN],tot = 0,mu[MAXN];

void sieve()

{

	for(ll i = 2;i < MAXN;++i)isprime[i] = true;

	mu[1] = 1;

	for(ll i = 2;i < MAXN;++i)

	{

		if(isprime[i])

		{

			prime[++tot] = i;

			mu[i] = -1;

		}

		for(ll j = 1;j <= tot && i * prime[j] < MAXN;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0){mu[i * prime[j]] = 0;break;}

			else{mu[i * prime[j]] = -1 * mu[i];}

		}

	}

	return;

}

ll calc(ll k)

{

	ll res = 0;

	for(ll i = 1;i * i <= k;++i)

	{

		res += mu[i] * (k / (i * i));

	}

	return res;

}

void work()

{

	ll k;

	scanf("%lld",&k);

	ll l = k,r = 2 * k,mid;

	while(l < r)

	{

		mid = ((l + r) >> 1);

		if(calc(mid) >= k)r = mid;

		else l = mid + 1;

	}

	printf("%lld\n",l);

	return;

}

int main()

{

	sieve(); 

	ll testcases;

	scanf("%lld",&testcases);

	while(testcases--)work();

	return 0;

}