P4318 完全平方数
考虑二分后，问题转化为 $n$ 以内有多少个不含平方因子的数。
Solution I
记 $F(x)$ 表示所有包含因子 $x ^ 2$ 的数的个数，这个很好算，答案为 $\lfloor \frac n {x ^ 2} \rfloor$ 。直接这样计算会算多，因为 $x$ 的倍数的答案也被算入了。即 $F(x) = \sum _ {x | d} f(d)$ 。上莫反，得到 $f(n) = \sum _ {n | d} \mu (\frac d n) F(d)$ 。
那么有 $f(1) = \sum _ {d = 1} ^ \infty \mu(d) \lfloor \frac n {d ^ 2} \rfloor$ 。
Solution II
记 $g (x)$ 表示 $x$ 的最大平方因子，求 $\sum _ {i = 1} ^ n [f(i) = 1]$
$$
\begin {aligned}
ANS &= \sum _ {i = 1} ^ n \sum _ {d | g(i)} \mu(d) \\
&= \sum _ {i = 1} ^ n \sum _ {d ^ 2 | i} \mu(d) \\
&= \sum _ {d = 1} ^ n \mu(d) \lfloor \frac n {d ^ 2} \rfloor
\end {aligned}
$$
事实上，$[g(x) = 1] = \mu ^ 2(x)$ ，也就是说 $\mu ^ 2 (x) = \sum _ {d ^ 2 | x} \mu(d)$ 。
查看代码
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
| #include <cstdio>
using namespace std;
template <class Type>
void read (Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
flag |= c == '-';
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 3) + (x << 1) + c - '0';
if (flag) x = ~x + 1;
}
template <class Type, class ...Rest>
void read (Type &x, Rest &...y) { read(x); read(y...); }
template <class Type>
void write (Type x)
{
if (x < 0) putchar('-'), x = ~x + 1;
if (x > 9) write(x / 10);
putchar('0' + x % 10);
}
typedef unsigned int UI;
const int N = 1e5 + 10;
bool vis[N];
int cnt, p[N], mu[N];
void init ()
{
vis[1] = true;
mu[1] = 1;
for (int i = 1; i < N; ++i)
{
if (!vis[i])
mu[p[++cnt] = i] = -1;
for (int j = 1; j <= cnt && i * p[j] < N; ++j)
{
vis[i * p[j]] = true;
if (i % p[j] == 0)
{ mu[i * p[j]] = 0; break; }
mu[i * p[j]] = mu[i] * mu[p[j]];
}
}
}
int calc (int n)
{
int res = 0;
for (int i = 1; i * i <= n; ++i)
res += mu[i] * (n / i / i);
return res;
}
int main ()
{
init();
int T; read(T);
for (int k; T; --T)
{
read(k);
int l = 1, r = 2e9, res;
while (l <= r)
{
int mid = (UI)l + r >> 1;
calc(mid) >= k ? (res = mid, r = mid - 1) : l = mid + 1;
}
write(res), puts("");
}
return 0;
}
|