GESP 题解库 / 5 级题解 / [GESP202312 五级] 小杨的幸运数 · 第 16 / 23 题
GESP202312 五级 · B3929 · 中等

小杨的幸运数

判断每个数是否幸运数;否则给出它"幸运化"(不断 +1)后的结果。

📊
N ≤ 2 × 10⁵
询问次数
🔢
x ≤ 10⁶+1
数值范围
⚡
O(MAXV log MAXV)
预处理
🎯
筛法标记倍数 + 后缀最近
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

规定:

给定 N 个 x,若 x 是幸运数输出 lucky,否则输出幸运化后的结果。

💡
人话翻译:分两步——① 预处理:把 1 ~ MAXV 中所有"幸运数"标记出来(对每个超级幸运数 p,把 p 的所有倍数标记);② 预处理"下一个幸运数":从后往前扫一遍,记录每个位置之后最近的幸运数,之后每次询问就能 O(1) 回答。
这是"打表预处理 + O(1) 查询"的经典套路。

🔍 关键词提取

筛法标记倍数后缀最近值离线预处理O(1) 查询

已知条件

项目说明
输入第一行 a、N;随后 N 行每行一个 x
输出每行 lucky 或幸运化结果
数据范围a ≤ 10⁶,N ≤ 2 × 10⁵,x ≤ 10⁶ + 1
超级幸运数完全平方数 k² 且 ≥ a
幸运数超级幸运数的倍数

需要解决的问题

02
思维导图
整理解题思路的全貌
🍀 标记幸运数 + 后缀最近
📐 定义链
超级幸运数 = k² ≥ a
幸运数 = 超级幸运数的倍数
幸运化 = 不断 +1 到最近的幸运数
注意:小于 a 的平方数不算
🎨 第一步标记
枚举 k 使 k² ≥ a 且 ≤ MAXV
把 k² 的所有倍数标记
调和级数复杂度
总约 1.6 × MAXV
🔗 第二步后缀
从 MAXV 往前扫
lucky[i] 为真 → nxt[i] = i
否则 nxt[i] = nxt[i+1]
查询 O(1)
⚠️ 易错点
表开太小(幸运化结果会超出 x 上限)
忘记标记超级幸运数自身
把小于 a 的平方数也当超级幸运数
发现 nxt 越界
03
样例手算推导
两个样例的验证

🧮 样例 1:a = 2

先找出超级幸运数与幸运数。

1
超级幸运数

所有 ≥ 2 的完全平方数:

2² = 4、3² = 9、4² = 16、5² = 25、…

注意 1² = 1 < 2,所以 1 不是超级幸运数

超级幸运数:4, 9, 16, 25, …

2
幸运数(超级幸运数的倍数)

4 的倍数:4, 8, 12, 16, 20, 24, …

9 的倍数:9, 18, 27, …

16 的倍数:16, 32, …(16 已在 4 的倍数中)

合并后从小到大:4, 8, 9, 12, 16, 18, 20, …

幸运数集合已确定

询问 x是幸运数吗幸运化结果输出
1否不断 +1:2、3 都不是,4 是 → 44
4是—lucky
5否6、7 不是,8 是 → 88
9是—lucky

输出 4、lucky、8、lucky ✓

🧮 样例 2:a = 16

这次 a 较大,最小超级幸运数是 16。

1
超级幸运数

≥ 16 的完全平方数:16, 25, 36, 49, 64, 81, 100, 121, 144, …

注意 9 = 3² < 16,所以 9 不是超级幸运数

超级幸运数:16, 25, 36, …

2
幸运数(从 16 起)

16 的倍数:16, 32, 48, 64, 80, 96, 112, 128, …, 1024, …

25 的倍数:25, 50, 75, 100, …

所以 1 ~ 15 里没有任何幸运数

1 ~ 15 全不是幸运数

询问 x输出说明
1161 ~ 15 都不是幸运数,最近的是 16
216同上
4164 < a=16,虽然是平方数但不合格
816同上
16lucky16 是超级幸运数
32lucky32 = 16 × 2
64lucky64 = 16 × 4
128lucky128 = 16 × 8
256lucky256 = 16 × 16
512lucky512 = 16 × 32
1024lucky1024 = 16 × 64

输出 16、16、16、16、lucky × 7 ✓

⚠️
注意 4 这个例子:4 = 2² 确实是完全平方数,但它小于 a = 16,所以不是超级幸运数,自然也不是幸运数,要输出幸运化结果 16。这是本题最容易搞错的地方——"完全平方数"和"超级幸运数"不是一回事。
04
解法对比
打表预处理 vs 每次暴力 +1

⚔️ 解法对比

🟢 离线打表 + O(1) 查询(推荐) 推荐

标记所有幸运数,再用后缀递推求"下一个幸运数"

  • 预处理 O(MAXV log MAXV)
  • 每次询问 O(1)
  • N = 2 × 10⁵ 时总耗时极少
  • 代码 25 行
💡
为什么能预处理:所有询问的数值范围是固定的(≤ 10⁶ 级别),所以可以一次性把整张表建好,之后每个询问只是查数组。

🟠 每个询问单独暴力 +1 并判定

对每个 x 不断 +1,每次判断是否幸运数

  • 判定单个数的代价高
  • 每次询问可能 +1 很多次
  • N = 2 × 10⁵ 时 必然超时
  • 且重复计算严重
⚠️
注意最坏情况:a = 10⁶ 时,x = 1 要 +1 到 10⁶ 才成为幸运数——单次询问就要 10⁶ 步,乘以 2 × 10⁵ 个询问就是 2 × 10¹¹,必然超时。

📈 性能对比

方案总复杂度可行性
打表 + 后缀O(MAXV log MAXV + N)✅ 稳过
逐次暴力 +1最坏 O(N × MAXV)❌ 超时
05
算法流程图
标记幸运数并递推最近值
开始读入 a、N;lucky[1..MAXV] 全为 false枚举 k,使 k² ≥ a 且 k² ≤ MAXV把 k² 以及它的所有倍数标记为 lucky从 MAXV 往前扫:nxt[i] = lucky[i] ? i : nxt[i+1]处理每个询问 xlucky[x] ? 输出 lucky : 输出 nxt[x]结束处理下一个询问
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🍀 幸运数判定器

第一行输入 a 和 N,随后 N 行输入要判断的数。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码

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

const int MAXV = 2100000;      // 需略大于 2 × 10^6

bool lucky[MAXV + 2];
int nxt[MAXV + 2];

int main() {
    int a, N;
    scanf("%d %d", &a, &N);

    // 第一步:标记所有幸运数
    // 超级幸运数 = 所有 k^2 且 k^2 >= a
    int k = 1;
    while ((long long)k * k < a) k++;          // 找到最小的 k 使 k^2 >= a
    for (; (long long)k * k <= MAXV; k++) {
        int p = k * k;                          // p 是超级幸运数
        for (int m = p; m <= MAXV; m += p)      // p 的所有倍数也是幸运数
            lucky[m] = true;
    }

    // 第二步:从后往前求"最近的下一个幸运数"
    nxt[MAXV + 1] = 0;                          // 0 表示不存在
    for (int i = MAXV; i >= 1; i--)
        nxt[i] = lucky[i] ? i : nxt[i + 1];

    // 回答询问
    while (N--) {
        int x;
        scanf("%d", &x);
        if (lucky[x]) printf("lucky\n");
        else          printf("%d\n", nxt[x]);
    }
    return 0;
}
🔑
while ((long long)k * k < a) k++; 在做什么?它在找最小的 k 使 k² ≥ a——这正好是最小的超级幸运数。注意用 (long long) 强制转换,因为 k * k 可能接近 int 上限。不能从 k = 1 开始标记!否则会把小于 a 的平方数(如 a=16 时的 4、9)错误地标记为超级幸运数。

📖 关键几行怎么看

代码作用为什么这样写
while ((long long)k*k < a) k++;起点跳过所有小于 a 的平方数
for (m = p; m <= MAXV; m += p)标记倍数超级幸运数的倍数都是幸运数
nxt[i] = lucky[i] ? i : nxt[i+1];后缀递推从后往前,一次扫描得到所有"最近幸运数"
if (lucky[x])回答是则 lucky,否则输出 nxt[x]
⚠️
三个坑:① k 从 1 开始(应跳过 k² < a);② 表开得太小(a = 10⁶ 时 x = 10⁶+1 会幸运化成 2 × 10⁶);③ 忘记标记超级幸运数自身(循环从 m = p 开始保证包含)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
2 4
1 / 4 / 5 / 9
4
lucky
8
lucky
题面样例 1
16 11
1 2 4 8 16 32 64 128 256 512 1024
16
16
16
16
lucky × 7
题面样例 2
1 2
1 / 2
lucky
lucky
a = 1 时 1 也是超级幸运数
4 3
2 / 3 / 4
4
4
lucky
a = 4 时 1、2、3 都要幸运化到 4
✅
自查清单:① 跳过了 k² < a 吗?② 表够大吗?③ 后缀递推是从后往前吗?

🚨 易错点清单

⚠️
k 从 1 开始标记:应先用 while (k*k < a) k++; 跳过小平方数,否则 4、9 等会被误判。
⚠️
表开小:幸运化结果可能超过 x 的上限,MAXV 要开到约 2.1 × 10⁶。
⚠️
逐次暴力 +1:最坏会到 2 × 10¹¹ 次运算,必须打表。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

预处理时间
O(MAXV log MAXV)
每次询问
O(1)
空间
O(MAXV)
MAXV
约 2.1 × 10⁶

时间怎么算的?

空间都用在哪?

一个布尔数组 + 一个整数数组,各约 2.1 × 10⁶。

✅ 预处理约几百万次操作,瞬间完成;N = 2 × 10⁵ 次询问都是 O(1)。

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

🔗 常用技巧小抄

// "打表 + 后缀最近值"通用套路
// 第一步:标记所有满足条件的数
for (每个"基元" p) for (int m = p; m <= MAXV; m += p) good[m] = true;

// 第二步:从后往前求"最近的下一个满足条件的数"
nxt[MAXV + 1] = INF;
for (int i = MAXV; i >= 1; i--) nxt[i] = good[i] ? i : nxt[i + 1];

// 第三步:O(1) 回答
int ans = good[x] ? x : nxt[x];

// 找"最小的 k 使 k^2 >= a"
int k = 1; while ((long long)k * k < a) k++;   // 或 k = ceil(sqrt(a))

// 类似的"筛法标记倍数"套路
// - 埃氏筛:标记合数
// - 本题:标记超级幸运数的倍数

🌟 举一反三

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

能力点本题怎么用还能迁移到
筛法标记倍数把基元的倍数全部标记质数筛、倍数标记类问题
后缀最近值从后往前递推求"最近的下一个满足条件的数"
打表 + O(1) 查询用空间换时间询问多、值域固定的题目
🌟
思考题:如果题目改成"幸运化时是不断 −1"(往下找最近的幸运数),要改哪里?(提示:把后缀递推改成前缀递推——prv[i] = lucky[i] ? i : prv[i-1],从左往右扫一遍即可。"往前找"用前缀、"往后找"用后缀,这是同一个套路的两面。)