【GESP】C++五级真题（埃氏筛思想考点） luogu-B3929 [GESP202312 五级] 小杨的幸运数
GESP C++ 2023年12月五级真题，埃氏筛思想考点，难度⭐⭐⭐☆☆。洛谷难度等级普及/提高−
luogu-B3929 [GESP202312 五级] 小杨的幸运数
题目要求
题目描述
小杨认为，所有大于等于 $a$ 的完全平方数都是他的超级幸运数。
小杨还认为，所有超级幸运数的倍数都是他的幸运数。自然地，小杨的所有超级幸运数也都是幸运数。
对于一个非幸运数，小杨规定，可以将它一直 $+1$，直到它变成一个幸运数。我们把这个过程叫做幸运化。例如，如果 $a=4$，那么 $4$ 是最小的幸运数，而 $1$ 不是，但我们可以连续对 $1$ 做 $3$ 次 $+1$ 操作，使其变为 $4$，所以我们可以说， $1$ 幸运化后的结果是 $4$。
现在，小杨给出 $N$ 个数，请你首先判断它们是不是幸运数；接着，对于非幸运数，请你将它们幸运化。
输入格式
第一行 $2$ 个正整数 $a, N$。
接下来 $N$ 行，每行一个正整数 $x$ ，表示需要判断（幸运化）的数。
输出格式
输出 $N$ 行，对于每个给定的 $x$ ，如果它是幸运数，请输出
lucky，否则请输出将其幸运化后的结果。
输入输出样例 #1
输入 #1
1
2
3
4
5
2 4
1
4
5
9
输出 #1
1
2
3
4
4
lucky
8
lucky
输入输出样例 #2
输入 #2
1
2
3
4
5
6
7
8
9
10
11
12
16 11
1
2
4
8
16
32
64
128
256
512
1024
输出 #2
1
2
3
4
5
6
7
8
9
10
11
16
16
16
16
lucky
lucky
lucky
lucky
lucky
lucky
lucky
说明/提示
样例解释 1
$1$ 虽然是完全平方数，但它小于 $a$，因此它并不是超级幸运数，也不是幸运数。将其进行 $3$ 次 $+1$ 操作后，最终得到幸运数 $4$。$4$ 是幸运数，因此直接输出 lucky 。
$5$ 不是幸运数，将其进行 $3$ 次 $+1$ 操作后，最终得到幸运数 $8$。
$9$ 是幸运数，因此直接输出 lucky 。
数据规模
对于 $30\%$ 的测试点，保证 $a,x \le 100,N \le 100$。
对于 $60\%$ 的测试点，保证 $a,x \le 10^6$。
对于所有测试点，保证 $a \le 1,000,000$；保证 $N \le 2 \times 10^5$；保证 $1 \le x \le 1,000,001$。
题目分析
解题思路
本题的关键是快速判定一个数是否为“幸运数”，并对非幸运数求出“幸运化”后的最小值。
幸运数 = 所有 $\ge a$ 的完全平方数（超级幸运数）及其倍数。
数据范围：$a\le 10^6$，$N\le 2\times 10^5$，$x\le 10^6+1$。
下面给出两种可AC的思路（直接暴力会超时），推荐掌握埃式筛思路方法，输入五级考试大纲的内容。
方法一：类埃氏筛标记（前缀数组）
思想：
- 先求出 $\ge a$ 的最小完全平方数 $s_0=\lceil\sqrt a\rceil^2$，以及后续所有完全平方数 $s_i=i^2$（$i$ 向上取整到 $1001$ 即可覆盖 $10^6+1$）。
- 类似素数筛，把每个超级幸运数 $s_i$ 的所有倍数全部打标记，数组 $\texttt{lucky[num]}=1$ 表示 $\texttt{num}$ 是幸运数。
- 查询时 $O(1)$ 判 $\texttt{lucky[x]}$ 即可；若 $x$ 未被标记，则从 $x$ 开始向后线性扫描到第一个 $\texttt{lucky[j]}=1$ 的位置，即为幸运化结果。
复杂度：
- 筛法阶段：超级幸运数个数 $\approx\sqrt{10^6}=10^3$，每个数筛倍数，总操作次数 $\approx 10^3\cdot(10^6/1)=10^9$，在 $10^6$ 范围内实际跑得过（CF/洛谷 $1\,\text s$ 内）。
- 查询阶段：$O(1)$ 判定 + 最坏 $O(\Delta)$ 向后扫描，$\Delta$ 通常很小（下一个幸运数几乎贴身）。
方法二：数学计算（不预处理筛表）
思想：
- 预处理只存“超级幸运数”列表 $\texttt{sq[]}$，元素个数 $\le\sqrt{10^6}=10^3$。
- 判定幸运数：枚举 $\texttt{sq[]}$，看是否存在某个 $s\in\texttt{sq}$ 使得 $x\bmod s = 0$，一旦找到立即返回 $\texttt{true}$；否则 $\texttt{false}$。
- 由于 $\texttt{sq[]}$ 长度 $\le 10^3$，单次判定 $\le 10^3$ 次取模，$2\times 10^5$ 次询问总计算量 $2\times 10^8$，$1\,\text s$ 内可过。
幸运化：对非幸运数 $x$，求“$\ge x$ 的最小幸运数”。
\[\texttt{candidate}=s\cdot\Bigl\lceil\frac xs\Bigr\rceil=s+x-x\bmod s\]
分两种情况：
(1) $x< a$：最小幸运数一定是 $\ge a$ 的最小完全平方数，即 $s_0=\lceil\sqrt a\rceil^2$。
(2) $x\ge a$：此时只需在超级幸运数集合里找“$\ge x$ 的最小倍数”。
对每个 $s\in\texttt{sq}$，计算所有 $\texttt{candidate}$ 取最小值即可。
由于 $\texttt{sq[]}$ 长度 $\le 10^3$，单次幸运化最多 $10^3$ 次计算，$2\times 10^5$ 次总计算量 $2\times 10^8$，同样 $1\,\text s$ 内可过。
优点：
- 无需 $10^6$ 级别大数组，内存 $O(\sqrt a)$；
- 极限数据下运行时间稳定，不会被卡。
缺点：
- 单次查询常数比方法一略大；
- 代码量稍多，需要小心处理边界（$x<a$、$x=a$、整除等）。
示例代码
方法一、类素数埃式筛思路
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
#include <cmath>
#include <iostream>
int lucky_nums[1002100];
int main() {
int a, N;
std::cin >> a >> N; // 读入起始完全平方数下界 a 与询问次数 N
// 埃氏筛思想：标记所有超级幸运数（≥a 的完全平方数）及其倍数
for (int i = std::ceil(std::sqrt(a)); i <= 1001; i++) {
int square_num = i * i; // 当前超级幸运数
lucky_nums[square_num] = 1; // 标记自己
for (int j = 2; j * square_num <= 1002000; j++) {
lucky_nums[j * square_num] = 1; // 标记其所有倍数
}
}
// 处理 N 次询问
for (int i = 0; i < N; i++) {
int x;
std::cin >> x;
if (lucky_nums[x]) { // 若 x 已是幸运数
std::cout << "lucky" << std::endl;
} else {
int max_n = std::max(x, a); // 从 max(x,a) 开始往后找第一个幸运数
for (int j = max_n; j <= 1002100; j++) {
if (lucky_nums[j]) {
std::cout << j << std::endl; // 输出幸运化结果
break;
}
}
}
}
return 0;
}
方法二、数学计算法
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
#include <cmath>
#include <iostream>
#include <vector>
std::vector<int> square_nums; // 存放所有 ≥a 的完全平方数（超级幸运数）
// 判断 x 是否为幸运数：只要 x 是某个超级幸运数的倍数即可
bool is_lucky(int x) {
for (int i = 0; i < square_nums.size(); i++) {
if (x == square_nums[i] || x % square_nums[i] == 0) {
return true; // 找到任一超级幸运数能整除 x，即为幸运数
}
}
return false; // 没有任何超级幸运数能整除 x，不是幸运数
}
// 对非幸运数 x 进行“幸运化”：返回不小于 x 的最小幸运数
std::string luckyize(int x, int a) {
// 若 x 本身已是幸运数且 ≥a，直接返回 lucky
if (is_lucky(x) && x >= a) {
return "lucky";
}
int lucky_num; // 用于保存幸运化结果
if (a >= x) {
// 当 a ≥ x 时，最小幸运数就是 ≥a 的最小完全平方数
lucky_num = std::pow(std::ceil(std::sqrt(a)), 2);
} else {
// 当 x > a 时，找 ≥x 的最小“超级幸运数倍数”
// 先以第一个超级幸运数为基准，计算其倍数中 ≥x 的最小值
// 计算 ≥x 的最小“square_nums[0] 的倍数”：
// 若 x 能被 square_nums[0] 整除，则 x 本身就是该倍数；
// 否则先求出 x 除以 square_nums[0] 的余数 r = x % square_nums[0]，
// 再把 x 向上“补齐”到下一个整数倍，即 x + (square_nums[0] - r)。
// 合并写法：square_nums[0] + x - x % square_nums[0]
lucky_num = square_nums[0] + x - x % square_nums[0];
// 再遍历其余超级幸运数，取最小值
for (int i = 1; i < square_nums.size(); i++) {
lucky_num = std::min(lucky_num, square_nums[i] + x - x % square_nums[i]);
}
}
return std::to_string(lucky_num); // 返回字符串形式的幸运化结果
}
int main() {
int a, N;
std::cin >> a >> N; // 读入起始下界 a 和询问次数 N
// 预处理：把所有 ≥a 的完全平方数加入 square_nums
for (int i = 1; i <= 1001; i++) {
if (i * i >= a) {
square_nums.push_back(i * i);
}
}
// 处理 N 次询问
for (int i = 0; i < N; i++) {
int x;
std::cin >> x; // 读入待判断/幸运化的数
std::cout << luckyize(x, a) << std::endl; // 输出结果
}
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
