题目链接：BZOJ 2240
要求寻找 \(\sum_{i=1}^{n} \mu^2(i) = k\) 的最小 \(n\)。
根据莫比乌斯系数容斥
\[\sum_{i=1}^{n} \mu^2(i) = \sum_{i=1}^{\lfloor \sqrt{n} \rfloor} \mu^2(i) \lfloor \frac{n}{i^2} \rfloor \]
我们可以 \(O(\sqrt{n})\) 地求小于等于 \(n\) 的无平方因子数的个数，接着二分即可，时间复杂度 \(O(T \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
| #include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int MAX_N = 100000 + 5;
bool vis[MAX_N];
int mu[MAX_N], p[MAX_N], tot;
void linearSieve() {
vis[0] = vis[1] = 1;
mu[1] = 1;
for (int i = 2; i < MAX_N; ++i) {
if (!vis[i]) {
p[++tot] = i;
mu[i] = -1;
}
for (int j = 1; j <= tot && LL(i) * p[j] < MAX_N; ++j) {
vis[i * p[j]] = 1;
if (i % p[j] == 0) break;
else mu[i * p[j]] = mu[i] * mu[p[j]];
}
}
}
int T, k;
inline LL sum(LL x) {
LL ret = 0;
LL up = sqrt(x);
for (LL i = 1; i <= up; ++i) ret += mu[i] * (x / (i * i));
return ret;
}
int main() {
linearSieve();
scanf("%d", &T);
for (int cs = 1; cs <= T; ++cs) {
scanf("%d", &k);
LL l = 1, r = LL(1E10);
while (l < r) {
LL mid = (l + r) >> 1;
LL s = sum(mid);
if (s < k) l = mid + 1;
else r = mid;
}
printf("%lld\n", l);
}
return 0;
}
|