【题目描述】
小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些
数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而
这丝毫不影响他对其他数的热爱。
这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一
个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了
小X。小X很开心地收下了。
然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗？
【输入格式】
包含多组测试数据。文件第一行有一个整数 (T)，表示测试
数据的组数。
第 (2) 至第 (T+1) 行每行有一个整数 (K_i)，描述一组数据，含义如题目中所描述。
【输出格式】
含 (T) 行，分别对每组数据作出回答。第 (i) 行输出相应的
第 (K_i) 个不是完全平方数的正整数倍的数。
这种题一眼二分答案啊QWQ
然后问题就变成求1~x中有多少个合法的数了
当然是总数减不合法的
看一下不合法的怎么算
首先 (4=2^2) 的倍数都不合法 减掉(lfloor frac{n}{4}
floor)
然后 (9=3^2) 也不合法 减掉 (lfloor frac{n}{9}
floor)
(16)呢？显然(4)的时候已经算过了 跳过
(25)我们也跳过了 重点看一下(36)
注意到(36)的倍数在(4)和(9)的时候都被减了一次(因为(6=2 * 3)，所以(6^2=2^2 * 3^2)) 因为容斥 我们反而要加回来一个(lfloor frac{n}{36}
floor)
再看看我们做了哪些运算：$$ + lfloor frac{n}{4} floor * (-1) + lfloor frac{n}{9} floor * (-1) + lfloor frac{n}{16} floor * 0 + lfloor frac{n}{25} floor * (-1) + lfloor frac{n}{36} floor * 1$$
然后我们发现了美妙性质：(1sim x)中合法的数的个数 (=x-sumlimits_{i=1}^x mu(i)*lfloor frac{n}{i^2} floor)
没毛病 然后质数筛预处理一下莫比乌斯函数 二分(r)开到(2*10^{9})就够了
时间复杂度(O(sqrt{K} log{K}))
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
ll x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
return x * f;
}
ll t, n;
ll prime[100005], tot, mobius[100005];
bool np[100005];
inline void init() {
mobius[1] = 1;
for (ll i = 2; i <= 100000; i++) {
if (!np[i]) {
prime[++tot] = i;
mobius[i] = -1;
}
for (ll j = 1; j <= tot && i * prime[j] <= 100000; j++) {
np[i * prime[j]] = 1;
if (i % prime[j] == 0) {
mobius[i * prime[j]] = 0;
break;
} else mobius[i * prime[j]] = -mobius[i];
}
}
}
inline bool check(ll x) {
ll sum = x;
for (ll i = 2; i * i <= x; i++) {
sum += mobius[i] * (x / (i * i));
}
return sum >= n;
}
int main() {
t = read();
init();
while (t--) {
n = read();
ll l = 1, r = 10000000000, mid, ans;
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else l = mid + 1;
}
printf("%lld
", ans);
}
return 0;
}