[BZOJ2440]完全平方数

Description

$T$ 组数据。

每组数据给定 $k$,求出第 $k$ 个不是完全平方数的倍数的数。

$$
1 \le T \le 50, 1 \le k \le 10 ^9
$$

Solution

不是完全平方数的倍数,等价于 $\mu (x) \not = 0$。

可以先考虑二分一个 $x$,问题变为求出 $[1, x]$ 中有多少个 $i$ 满足 $\mu (i) \not = 0$。

考虑怎么算这个东西。

直接构造并反演

设 $f(i)$ 表仅为 $i ^2$ 的倍数,且不为其他完全平方数的倍数的数的个数。数的上限为 $x$,也就是这些数不能超过 $x$。

修正:$f(i)$ 的意义应当为除掉 $i ^2$ 后不是一个大于一的完全平方数的倍数的数的个数。

再令 $F(i) = \sum \limits _{i | d} ^x f(d)$。可以得到 $F(i)$ 的意义为是 $i ^2$ 的倍数的数的个数,则 $F(i) = \lfloor \frac x {i ^2} \rfloor$。

直接进行莫比乌斯反演(这是个和平常不一样的反演,是 $i | d$ 而非 $d | i$)得到

$$
f(i) = \sum _{i | d} ^n \mu (\frac d i) F(d)
$$

$f(1)$ 就是上面要求的(满足 $\mu(i) \not = 0$ 的)。则 $f(1) = \sum \limits _{d = 1} ^x \mu (d) \lfloor \frac x {i ^2} \rfloor$,因为出现了 $\lfloor \frac x {i ^2} \rfloor$,所以 $i$ 只需要枚举到 $\sqrt x$ 即可。

所以得到最终式:

$$
\sum _{i = 1} ^{\lfloor \sqrt x \rfloor} \mu(i) \lfloor \frac x {i ^2} \rfloor
$$

利用莫比乌斯函数容斥

考虑求出 $[1, x]$ 之间不含平方因子的数的个数。

可以知道答案为 $x$ 减去 1 个素数的平方的倍数的数的个数 + 2 个素数的积的平方的倍数 - …

可以发现这个容斥系数恰好为 $\mu$,因为 1 个素数减,2 个素数加,含平方因子数省略,很明显的 $\mu$ 的特征。

可以得到一个答案式:

$$
x + \sum _{i = 2} ^{\lfloor \sqrt x \rfloor} \mu (i) \lfloor \frac x {i ^2} \rfloor = \sum _{i = 1} ^{\lfloor \sqrt x \rfloor} \mu (i) \lfloor \frac x {i ^2} \rfloor
$$

注意这里枚举 $i$ 的意义就是枚举数,不是枚举有多少个平方因子等七里八里的东西。

一样只需要枚举到 $\sqrt x$。

Code

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
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <cmath>
#include <iostream>
#include <vector>
#include <bitset>

using namespace std;
using LL = long long;

const int maxN = 5e4 + 5;

int T, k;
int mu[maxN];
vector<int> prim;
bitset<maxN> vis;

void Shuffle(int n)
{
mu[1] = 1;
for (int i = 2; i <= n; ++i)
{
if (!vis[i])
mu[i] = -1, prim.push_back(i);
for (int j : prim)
{
int x = i * j;
if (x > n)
break;
vis.set(x);
if (i % j)
mu[x] = -mu[i];
else
break;
}
}
}

LL Getsum(LL x)
{
LL res = 0;
for (LL i = 1, tmp = sqrt(x); i <= tmp; ++i)
res += mu[i] * x / (i * i);
return res;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("wib.in", "r", stdin);
freopen("wib.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin >> T;
Shuffle(50000);
while (T--)
{
cin >> k;
LL l = 1, r = k * 2, mid;
while (l < r)
{
// cerr << l << ' ' << r << endl;
mid = (l + r) >> 1;
if (Getsum(mid) < k)
l = mid + 1;
else
r = mid;
}
cout << l << endl;
}
return 0;
}