完全平方数

题目大意

求从 11 开始第 kk 个不是完全平方数的整倍数的数,多组询问。

1k1,000,000,0001 \leqslant k \leqslant 1,000,000,000

1T501 \leqslant T \leqslant 50

题目链接

完全平方数 - Luogu 4318

题解

可以用容斥原理计算出小于等于 nn 的数中有多少个是完全平方数的整倍数,即加上 n4\frac{n}4n9\frac{n}9n25\frac{n}{25} 等质数的平方,再减去 n16\frac{n}{16}n36\frac{n}{36} 等有两个质因数的数的平方……我们发现,它们的系数就是对应数的莫比乌斯函数的定义(的相反数),因此可以直接算出小于等于 nn 的数中有多少个满足要求:

i=1nμ(i)ni2\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
#include <cstdio>
const int MAXN = 100005;
int prime[MAXN], mu[MAXN], primeCnt;
bool notPrime[MAXN];
void linearShaker() {
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("%lld\n", dichotomy(k));
}
return 0;
}