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

一、题目解读

洛谷题目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)循环递增查找第一个幸运数。

四、代码与注释

C++

#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. 缓冲处理防止边界问题。

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

来源：