数字选取 题解

题目分析

本题要求从 $1 \sim n$ 中选出尽可能多的整数，使得选出的任意两个不同的数都互质（最大公因数为 $1$）。我们需要求出这个最大数量。

关键点在于理解“互质”的含义：两个数互质，当且仅当它们没有任何共同的质因子。例如 $6=2\times3$ 和 $10=2\times5$ 有公共质因子 $2$，不互质；而 $8=2^3$ 和 $9=3^2$ 没有公共质因子，互质。

解题思路

要使选出的数尽量多，我们要充分利用每个质因子。观察发现：

• 数字 $1$ 与任何整数互质，所以一定可以选上。
• 对于每一个质数 $p$（如 $2,3,5,\dots$），如果我们选了含有质因子 $p$ 的某个数，那么就不能再选其他含有 $p$ 的数（否则这两个数不互质）。
• 但我们可以在 $1 \sim n$ 中选择 $p$ 的某个幂次 $p^k$（$k \ge 1$），不同质数的幂次之间天然互质（质因子互不相同）。
• 对于每个不超过 $n$ 的质数 $p$，$p$ 本身一定 $\le n$，因此至少可以选 $p$ 本身。这样我们就为每一个质数保留了一个数。

因此，一种最优的选法如下：

• 选取 $1$；
• 对于 $n$ 以内的每一个质数 $p$，选取 $p$（或它的某个幂次，如 $p^2$ 等，只要 $\le n$）。

可以证明，这种选法的数量就是最大可能值，因为每个质数对应的数必然互质，且 $1$ 不与任何冲突。如果尝试选更多，必然会在某个质数上选了两个含该质因子的数，导致不互质。

于是，答案等于：

其中 $\pi(n)$ 表示 $1 \sim n$ 中质数的个数。

以 $n=9$ 为例：质数有 $2,3,5,7$ 共 $4$ 个，答案 $1+4=5$，可选出 $\{1,5,7,8,9\}$（这里 $8$ 是 $2$ 的幂，$9$ 是 $3$ 的幂）。

算法说明

题目转化为：求 $1 \sim n$ 内的质数个数。

由于 $n \le 10^5$，可以使用埃拉托色尼筛或线性筛（欧拉筛）。参考代码采用了线性筛，其优点是每个合数只被其最小的质因子筛掉一次，时间复杂度更低。

线性筛步骤：

1. 初始化 cnt = 0，数组 p 存储质数，np[i] 表示 $i$ 是否为合数。
2. 遍历 $i$ 从 $2$ 到 $n$：
   • 若 np[i] == false，则 $i$ 是质数，存入 p[++cnt]。
   • 用当前质数表 p[j] 筛掉 i * p[j]，标记 np[i * p[j]] = true。
   • 如果 i % p[j] == 0，说明 p[j] 是 $i$ 的最小质因子，跳出内层循环，保证每个合数只被筛一次。
3. 最终 cnt 即为质数个数。

输出 1 + cnt 即可。

时间复杂度分析

线性筛的时间复杂度为 $O(n)$。对于 $n \le 10^5$，可以在极短时间内完成，满足本题时间限制。

空间复杂度为 $O(n)$，存储标记数组和质数表，也完全在内存限制内。

参考代码

cpp
复制
1#include <cstdio>
2using namespace std;
3
4const int N = 1e5 + 5;
5int n, p[N], cnt;      // p[] 存质数，cnt 统计质数个数
6bool np[N];            // np[i] 表示 i 是否为合数
7
8int main() {
9    scanf("%d", &n);
10    
11    // 线性筛求 1~n 的质数个数
12    for (int i = 2; i <= n; i++) {
13        if (!np[i]) p[++cnt] = i;          // i 是质数
14        for (int j = 1; j <= cnt && i * p[j] <= n; j++) {
15            np[i * p[j]] = true;           // 筛掉合数
16            if (i % p[j] == 0) break;      // 保证每个合数只被最小质因子筛掉
17        }
18    }
19    
20    // 答案 = 1（数字1） + 质数个数
21    printf("%d\n", 1 + cnt);
22    return 0;
23}

代码解释

• np[i] 初始为 false，当遇到 !np[i] 时，说明 $i$ 未被任何小于它的质数筛掉，因此 $i$ 是质数，存入数组并增加计数。
• 内层循环用当前的质数 p[j] 去筛 i * p[j]，一旦 i % p[j] == 0，说明 p[j] 是 $i$ 的最小质因子，继续用更大的质数筛会出现重复，故跳出循环。
• 最后输出 1 + cnt，即 $1 + \pi(n)$。

---

小结：本题看似是一道组合选取问题，但通过分析互质的本质，转化为统计 $n$ 以内质数个数的问题，考察了数论基础与筛法的实现。