题目大意
求从 (1) 开始第 (k) 个不是完全平方数的整倍数的数，多组询问。
(1 leqslant k leqslant 1,000,000,000)
(1 leqslant T leqslant 50)
题目链接
BZOJ 2440
题解
可以用容斥原理计算出小于等于 (n) 的数中有多少个是完全平方数的整倍数，即加上 (frac{n}4)、(frac{n}9)、(frac{n}{25}) 等质数的平方，再减去 (frac{n}{16})、(frac{n}{36}) 等有两个质因数的数的平方……我们发现，它们的系数就是对应数的莫比乌斯函数的定义（的相反数），因此可以直接算出小于等于 (n) 的数中有多少个满足要求： [
sum_{i = 1}^{lfloor sqrt{n} rfloor} mu(i) * frac{n}{i^2}
] 线性筛预处理出莫比乌斯函数即可。
代码
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
|
const int MAXN = 100005;
int prime[MAXN], mu[MAXN], primeCnt;
bool notPrime[MAXN];
void () {
notPrime[0] = notPrime[1] = true;
mu[1] = 1;
for (int i = 2; i < MAXN; i++) {
if (!notPrime[i]) {
prime[++primeCnt] = i;
mu[i] = -1;
}
for (int j = 1; j <= primeCnt && i * prime[j] < MAXN; j++) {
notPrime[i * prime[j]] = true;
if (i % prime[j] == 0) {
mu[i * prime[j]] = 0;
break;
} else {
mu[i * prime[j]] = -mu[i];
}
}
}
}
long long check(long long x) {
long long res = 0;
for (long long i = 1; i * i <= x; i++) res += mu[i] * x / i / i;
return res;
}
long long dichotomy(int k) {
long long l = 1, r = (long long) MAXN * MAXN;
while (l < r) {
long long mid = l + (r - l) / 2;
if (check(mid) >= k) r = mid;
else l = mid + 1;
}
return l;
}
int main() {
linearShaker();
int T;
scanf("%d", &T);
while (T--) {
int k;
scanf("%d", &k);
printf("%lldn", dichotomy(k));
}
return 0;
}
|
近期评论