202312-小杨的幸运数(luogu-B3929)

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

4 
lucky 
8 
lucky

输入输出样例 #2

输入 #2

输出 #2

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$ 的最小幸运数”。
分两种情况：
(1) $x< a$ ：最小幸运数一定是 $\ge a$ 的最小完全平方数，即 $s_0=\lceil\sqrt a\rceil^2$ 。
(2) $x\ge a$ ：此时只需在超级幸运数集合里找“ $\ge x$ 的最小倍数”。
对每个 $s\in\texttt{sq}$ ，计算
$\texttt{candidate}=s\cdot\Bigl\lceil\frac xs\Bigr\rceil=s+x-x\bmod s$
所有 $\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$ 、整除等）。

示例代码

方法一、类素数埃式筛思路

#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;
}

方法二、数学计算法

#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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2025年11月2日

202309-巧夺大奖(luogu-B3872)202312-烹饪问题(luogu-B3930)