GESP 题解库 / 5 级题解 / [GESP202403 五级] B-smooth 数 · 第 13 / 23 题
GESP202403 五级 · B3969 · 简单

B-smooth 数

统计不超过 n 且最大质因子不超过 B 的正整数个数。

📊
n, B ≤ 10⁶
数据范围
🔢
int
数值类型
⚡
O(n log log n)
时间复杂度
🎯
筛法反向标记
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

若一个正整数的最大质因子不超过 B,则称它为 B-smooth 数。

给定 n 和 B,求不超过 n 的 B-smooth 数有多少个。

💡
人话翻译:直接求"最大质因子"有点绕,换个角度——反过来标记"不合格的数":凡是含有大于 B 的质因子的数都不是 B-smooth 数。所以先筛出所有质数,再把每个大于 B 的质数的所有倍数标记为不合格,剩下的就是答案。

🔍 关键词提取

B-smooth质因子埃氏筛反向标记

已知条件

项目说明
输入两个正整数 n、B
输出不超过 n 的 B-smooth 数的个数
数据范围1 ≤ n, B ≤ 10⁶
定义最大质因子 ≤ B
特例1 是 B-smooth 数(没有质因子)

需要解决的问题

02
思维导图
整理解题思路的全貌
🔍 反向标记大质因子的倍数
🧠 定义转化
最大质因子 ≤ B
⟺ 不含任何 > B 的质因子
改判为"标记不合格的数"
剩下的即答案
📊 筛质数
埃氏筛出 ≤ n 的质数
再对 p > B 处理
p 的所有倍数标记不合格
调和级数复杂度
✅ 统计
合格 = 未被标记
1 也算合格
遍历 1 ~ n 计数
输出个数
⚠️ 易错点
忘记 1 算 B-smooth
B ≥ n 时全部合格(可直接输出 n)
用试除法逐个分解(会超时)
只标记 p 本身忘记倍数
03
样例手算推导
样例的逐步标记

🧮 样例:n = 10,B = 3,答案 7

先筛出 ≤ 10 的质数,再对 > 3 的质数标记倍数。

1
筛出 ≤ 10 的质数

2, 3, 5, 7

质数:2、3、5、7

2
对 p = 5(> B = 3)标记倍数

5, 10 被标记为不合格

20 超出范围不管

不合格:5、10

3
对 p = 7(> B = 3)标记倍数

7 被标记为不合格

14 超出范围

不合格:5、7、10

数质因数分解最大质因子≤ B = 3?合格
1(无)—✅(空真)是
222✅是
333✅是
42²2✅是
555❌否
62 × 33✅是
777❌否
82³2✅是
93²3✅是
102 × 55❌否

合格的有 1、2、3、4、6、8、9 共 7 个 ✓

🔑
注意 1 的处理:1 没有质因子,"最大质因子不超过 B"对它空真成立——所以 1 算 B-smooth。这一点在样例里得到确认:7 个数中包含 1。很多同学会漏掉 1,白白丢分。

🧮 两个极端的边界

情形结果原因
B ≥ n答案 = n所有 ≤ n 的数的质因子都 ≤ n ≤ B
B = 1答案 = 1只有 1 合格(2 的最小质因子是 2 > 1)
n = 1答案 = 1只有 1
n = 10, B = 10答案 = 10全部合格
⚠️
关于 B = 1 的验证:任何大于 1 的整数都有至少一个质因子,而最小的质因子是 2 > 1,所以除 1 以外全不合格。这可以用来自测代码的边界处理。
04
解法对比
反向标记 vs 逐个数分解

⚔️ 解法对比

🟢 反向标记(推荐) 推荐

筛出质数,把 > B 的质数的倍数标为不合格,统计剩余

  • 时间 O(n log log n)
  • n = 10⁶ 时约 3 × 10⁶
  • 代码 20 行
  • 统一处理所有数
💡
复杂度估算:标记量是 Σp>B n/p。最坏情况 B = 1 时,约 Σp≤n n/p ≈ n ln ln n ≈ 3 × 10⁶。完全够快。

🟠 对每个数分解质因数

逐个求最大质因子,判断是否 ≤ B

  • 每个数 O(√x)
  • 总数约 10⁶ × 10³ = 10⁹
  • 可能超时
  • 代码直观但慢
⚠️
对比量级:逐个数分解需要 10⁹ 级别,而反向标记只需 3 × 10⁶ 级别——差了三个数量级。这正是"筛法式批量处理胜过"逐个处理"的典型例子。

📈 性能对比

方案运算量(n = 10⁶)可行性
反向标记约 3 × 10⁶✅ 稳过
逐个分解约 10⁹❌ 可能超时
05
算法流程图
筛质数后反向标记倍数
开始读入 n、B;bad[1..n] 全为 false用埃氏筛找出 1 ~ n 的所有质数遍历每个质数 pp 是否大于 B?是 ✓把 p 的所有倍数标记为 bad否 ✗跳过统计 1 ~ n 中未被标记的数,输出个数结束处理下一个质数
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔍 B-smooth 计数

输入 n 和 B,程序会标记不合格的数并统计 B-smooth 数。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

bool isP[MAXN];      // 是否为质数
bool bad[MAXN];      // 是否不合格(含有 > B 的质因子)

int main() {
    int n, B;
    scanf("%d %d", &n, &B);

    // 埃氏筛:找出 1 ~ n 的所有质数
    for (int i = 0; i <= n; i++) isP[i] = true;
    isP[0] = isP[1] = false;
    for (int i = 2; (long long)i * i <= n; i++)
        if (isP[i])
            for (int j = i * i; j <= n; j += i) isP[j] = false;

    // 对每个大于 B 的质数,标记它的所有倍数
    for (int p = 2; p <= n; p++) {
        if (isP[p] && p > B) {
            for (int m = p; m <= n; m += p)
                bad[m] = true;
        }
    }

    // 统计合格(含 1)
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (!bad[i]) ans++;

    printf("%d\n", ans);
    return 0;
}
🔑
为什么标记倍数时从 m = p 开始(而不是 p * p)?因为在这里我们要标记 p 本身——p > B 说明 p 的最大质因子是 p,本身就不合格。这与"埃氏筛标记合数"不同(那里 p 本身是质数,所以从 p² 开始)。两处起点不同,务必分清。

📖 关键几行怎么看

代码作用为什么这样写
isP[0] = isP[1] = false筛法特殊值0 和 1 不是质数
if (isP[p] && p > B)筛选条件只处理"大于 B 的质数"
for (m = p; m <= n; m += p)标记倍数从 p 开始(p 本身也不合格)
for (i = 1; i <= n; i++) if (!bad[i]) ans++统计从 1 开始,让 1 被计入
⚠️
三个坑:① 统计时从 2 开始(漏掉 1);② 标记倍数从 p * p 开始(漏掉 p 本身);③ 用逐个分解代替筛法(可能超时)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
10 37题面样例:{1,2,3,4,6,8,9}
1 11只有 1
5 11B = 1 时只有 1 合格
20 252-smooth 数:1、2、4、8、16
10 1010B ≥ n 时全部合格
100 5运行验证更大的规模
✅
自查清单:① 1 算进去了吗?② 标记倍数从 p 开始吗?③ 用的是筛法吗?

🚨 易错点清单

⚠️
漏掉 1:1 没有质因子,"最大质因子 ≤ B"空真成立,所以 1 是 B-smooth 数。
⚠️
标记起点错:应写成 for (m = p; ...),因为 p 本身(> B)也不合格。
⚠️
逐个分解:复杂度约 10⁹,可能超时,要用筛法批量标记。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n log log n)
空间复杂度
O(n)
n 最大
10⁶
标记量
约 3 × 10⁶

时间怎么算的?

空间都用在哪?

两个长度为 n + 1 的布尔数组。

✅ 约几百万次操作,瞬间完成。相比逐个分解的 10⁹,快了三个数量级。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 反向标记模板:从"满足定义"转化为"排除不合格"
for (int p = 2; p <= n; p++)
    if (isP[p] && p > B)
        for (int m = p; m <= n; m += p) bad[m] = true;

// 另一种写法:直接求每个数的最大质因子(线性筛)
int mpf[N];                 // 最大质因子
for (int i = 2; i <= n; i++) {
    if (!mpf[i]) {          // i 是质数
        for (int j = i; j <= n; j += i) mpf[j] = i;
    }
}
// 然后 mpf[i] <= B 即为 B-smooth

// C++17 求质因数分解(配合试除)
// 用 __gcd、__builtin_popcount 等内置函数提高效率

// 复杂度速记
// 埃氏筛:O(n log log n)
// Σ_{p <= n} n/p ≈ n ln ln n
// 逐个试除分解:O(n√n)

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
反向标记改判为"排除不合格"含"最大/最小质因子"约束的计数题
筛法批量处理调和级数复杂度所有涉及"倍数的性质"的统计
1 的特殊性没有质因子,空真成立所有质因子相关定义都要留意
🌟
思考题:如果题目改成"求最大质因子恰好为 B 的数的个数",该怎么算?(提示:用容斥——"最大质因子 ≤ B 的个数" 减去 "最大质因子 ≤ B−1 的个数",(注意 B 需要是质数,否则答案为 0)。把"恰好"转化为"两个前缀相减",是很常用的计数技巧。)