B-smooth 数 题解

题目分析

我们需要统计在 $1$ 到 $n$ 之间，有多少个正整数的最大质因子不超过 $B$。这里的最大质因子是指：对一个大于 $1$ 的正整数做质因数分解后，所有质因子中最大的那个；对于 $1$，它没有质因子，题目中将其视为满足条件的数（$1$ 永远被计入答案，因为它没有质因子可以超过任何 $B$）。

数据范围中 $n, B \le 10^6$，因此我们有机会用 $O(n)$ 或 $O(n \log n)$ 的预处理来完成统计。

解题思路

如果我们能够求出 $1 \sim n$ 中每个正整数的最大质因子，那么只需要遍历一遍，统计最大质因子 $\le B$ 的数的个数即可。现在的问题转化为：如何高效地求出 $1 \sim n$ 每个数的最大质因子？

利用筛法求最大质因子

线性筛（欧拉筛）可以在 $O(n)$ 的时间内求出 $1 \sim n$ 中每个数的最小质因子，稍加改造就可以求出最大质因子。

回忆线性筛的过程：

• 从小到大枚举 $i$（$2 \sim n$）。
• 如果 $i$ 是质数，将其加入质数列表，并记录它本身是自己的最大质因子。
• 然后用每一个质数 $p$ 去筛掉合数 $i \times p$。
• 在线性筛中，每个合数只会被它的最小质因子筛掉一次。

当我们用 $i$ 和质数 $p$ 构造合数 $x = i \times p$ 时，$x$ 的质因子集合是 $i$ 的质因子集合再加上 $p$。因此我们可以用下面这个关系维护最大质因子：

这是因为 $x$ 的所有质因子包括 $i$ 的质因子和 $p$ 本身，它们中最大的一个就是 $\max(i$ 的最大质因子$, p)$。

但要注意，当 $i$ 是 $p$ 的倍数时，$p$ 也是 $i$ 的一个质因子，已经被包含在 $\text{max\_prime\_factor}(i)$ 中，上述公式依然成立。

我们还需要处理 $i=1$ 的情况：$1$ 的最大质因子可以设为 $1$（或者 $0$，只要保证后续比较时它不会错误地大于某个质数即可）。对于本题来说，我们只需在最后统计时把 $1$ 也当作满足条件的数计入答案。

算法说明

1. 初始化一个布尔数组 vis 标记是否被筛掉，一个整型数组 mx 记录每个数的最大质因子，以及一个空的质数列表 prime。
2. 令 mx[1] = 1。
3. 从 $i=2$ 到 $n$ 遍历：
   • 若 !vis[i]，说明 $i$ 是质数，执行：
     • mx[i] = i；
     • 将 $i$ 加入 prime。
   • 对于 prime 中的每个质数 $p$：
     • 如果 $i\times p>n$，跳出循环。
     • 标记 vis[i * p] = true。
     • 更新 mx[i * p] = max(mx[i * p], max(mx[i], p))。
       （因为同一个合数理论上只会被筛一次，所以直接用 = 也是可以的；参考代码中用了 max 来确保安全。）
     • 如果 $i \bmod p == 0$，说明 $p$ 是 $i$ 的最小质因子，根据线性筛原理跳出循环，保证每个合数只被最小质因子筛掉。
4. 筛法结束后，我们得到了每个数的最大质因子。遍历 $1 \sim n$，统计 mx[i] <= B 的个数，输出答案。

为什么这样是对的呢？

• 在线性筛中，每个合数 $x$ 会被表示为 $i \times p$，其中 $p$ 是 $x$ 的最小质因子，$i$ 是一个不小于 $p$ 的正整数。此时 $x$ 的全部质因子就是 $i$ 的全部质因子加上 $p$。用 $\max(\text{mx}[i], p)$ 更新 $\text{mx}[x]$ 就能正确计算出最大质因子。
• 对于质数，最大质因子就是它自己，我们在筛法开始时设置即可。
• 对于 $1$，它的最大质因子我们设为 $1$，因为 $B \ge 1$，所以 $1$ 会被自动统计到。

时间复杂度分析

线性筛的外层循环是 $O(n)$，内层对每个 $i$ 只会处理若干次质数，并且每个合数只被筛一次，整个筛法复杂度为 $O(n)$。最后遍历 $1 \sim n$ 统计答案的复杂度也是 $O(n)$。总时间复杂度为 $O(n)$，在 $n=10^6$ 时完全可以轻松通过。

空间复杂度方面，我们需要长度为 $n+5$ 左右的 vis 和 mx 数组，以及质数列表，空间为 $O(n)$，在 $256\text{MB}$ 的内存限制下绰绰有余。

参考代码

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5    int n, B;
6    cin >> n >> B;
7
8    // vis 标记是否被筛掉，mx 记录最大质因子
9    vector<bool> vis(n + 5, false);
10    vector<int> mx_prime_factor(n + 5, 0);
11    vector<int> prime;
12
13    mx_prime_factor[1] = 1;  // 1 的最大质因子设为 1
14
15    for (int i = 2; i <= n; i++) {
16        if (!vis[i]) {                // i 是质数
17            mx_prime_factor[i] = i;
18            prime.push_back(i);
19        }
20        for (int p : prime) {         // 用质数 p 筛合数
21            if (1ll * p * i > n)      // 注意用 1ll 防止乘法溢出
22                break;
23            vis[i * p] = true;
24            // 合数 i*p 的最大质因子是 max( i 的最大质因子, p )
25            mx_prime_factor[i * p] = max(mx_prime_factor[i * p],
26                                         max(mx_prime_factor[i], p));
27            if (i % p == 0)           // p 是 i 的最小质因子，跳出
28                break;
29        }
30    }
31
32    int ans = 0;
33    for (int i = 1; i <= n; i++) {
34        if (mx_prime_factor[i] <= B)
35            ans++;
36    }
37    cout << ans << endl;
38    return 0;
39}

代码解释

• 数组 mx_prime_factor 的下标对应 $1 \sim n$ 每一个数，其值存储该数的最大质因子。
• 核心转移：当用 $i$ 和 $p$ 筛去 $i \times p$ 时，由于 $i \times p$ 的所有质因子是 $i$ 的所有质因子以及 $p$ 的并集，因此最大质因子可以直接用 max(mx_prime_factor[i], p) 来更新。
• 利用线性筛的特性，每个合数只会被它的最小质因子筛一次，所以我们只需要在筛去它的第一时间进行更新，后续不再更改。
• 最后遍历统计 mx_prime_factor[i] <= B 的数量，输出即可。