【题目描述】
小 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} \rfloor$
然后$9=3^2$也不合法 减掉$\lfloor \frac{n}{9} \rfloor$
$16$呢?显然$4$的时候已经算过了 跳过
$25$我们也跳过了 重点看一下$36$
注意到$36$的倍数在$4$和$9$的时候都被减了一次(因为$6=2 * 3$,所以$6^2=2^2 * 3^2$) 因为容斥 我们反而要加回来一个$\lfloor \frac{n}{36} \rfloor$

再看看我们做了哪些运算:$+ \lfloor \frac{n}{4} \rfloor * (-1) + \lfloor \frac{n}{9} \rfloor * (-1) + \lfloor \frac{n}{16} \rfloor * 0 + \lfloor \frac{n}{25} \rfloor * (-1) + \lfloor \frac{n}{36} \rfloor * 1$

然后我们发现了美妙性质:$1\sim x$中合法的数的个数$=x-\sum\limits_{i=1}^x \mu(i)*\lfloor \frac{n}{i^2} \rfloor$

没毛病 然后质数筛预处理一下莫比乌斯函数 二分$r$开到$2*10^{9}$就够了

时间复杂度$O(\sqrt{K} \log{K})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#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\n", ans);
}
return 0;
}

评论