GESP五级算法题解：小杨的幸运数字（洛谷B3929）代码分析...

19339201706 · 发表于昨天 10:29

一、题目解读

洛谷题目B3929“小杨的幸运数字”要求处理一系列查询数字x，将其转化为≥x的最小幸运数字。幸运数字定义为：≥a的完全平方数的倍数。题目难点在于高效判断和生成幸运数，避免超时。

二、解题思路

采用“预生成+哈希表”策略：

1. 分步生成：先找出≥a的所有完全平方数（超级幸运数），再生成其倍数（幸运数）。

2. 哈希加速：使用unordered_set存储幸运数，实现O(1)查询。

3. 边界优化：通过预处理查询数组的最大值，缩小生成范围，避免无效计算。

三、解题步骤

1. 输入与预处理：读取N个查询，记录最大值max_x，并预留1000缓冲避免边界溢出。

2. 生成幸运数集合：调用generateLuckyNumbers(a, max_x+1000)，分两层循环生成超级幸运数及其倍数，存入哈希集。

3. 查询处理：若x本身为幸运数直接输出；否则通过makeLucky(x)循环递增查找第一个幸运数。

四、代码与注释

#include iostream
#include vector
#include cmath
#include unordered_set
using namespace std;
// 生成幸运数集合（超级幸运数+倍数）
unordered_set<int> generateLuckyNumbers(int a, int max_x) {
unordered_set<int> lucky_numbers;
for (int i = ceil(sqrt(a)); i <= max_x; i++) { // 从a的平方根开始找完全平方数
int super_lucky = i * i;
lucky_numbers.insert(super_lucky);
for (int j = 2; super_lucky * j <= max_x; j++) { // 生成倍数
lucky_numbers.insert(super_lucky * j);
}
}
return lucky_numbers;
}
// 查找比x大的最小幸运数
int makeLucky(int x, const unordered_set<int>& lucky_numbers) {
while (true) {
if (lucky_numbers.count(x)) return x; // 若x在集合中直接返回
x++;
}
}
int main() {
int a, N;
cin >> a >> N;
vector<int> queries(N);
int max_x = 0;
for (int i = 0; i < N; i++) {
cin >> queries[i];
if (queries[i] > max_x) max_x = queries[i];
}
unordered_set<int> lucky_numbers = generateLuckyNumbers(a, max_x + 1000); // 生成幸运数集合
for (int x : queries) {
if (lucky_numbers.count(x)) {
cout << "lucky" << endl;
} else {
cout << makeLucky(x, lucky_numbers) << endl;
}
}
return 0;
}

复制代码

五、总结

本解法通过“预生成+哈希表”将时间复杂度优化至O(N+√a)，空间复杂度O(幸运数数量)。关键在于：

1. 精准控制生成范围，避免冗余计算；

2. 利用哈希表快速判断幸运数；

3. 缓冲处理防止边界问题。

该策略适用于大规模数据的高效处理，是解决此类数学分类问题的典型思路。