12967.小杨的幸运数

markdown
复制
1# 小杨的幸运数 题解
2
3## 题目分析
4
5本题定义了两类数：
6
7- **超级幸运数**：所有大于等于 $a$ 的完全平方数。例如 $a=4$ 时，超级幸运数为 $4,9,16,25,\dots$
8- **幸运数**：所有超级幸运数的倍数。也就是说，如果一个数是某个超级幸运数的整数倍，那么它就是幸运数。
9
10现在给出 $N$ 个正整数，我们需要对每个数判断是否为幸运数。如果是，输出 `lucky`；否则，输出将其不断 $+1$ 后第一次变成幸运数的结果（即下一个幸运数）。
11
12数据范围：$a \le 10^6$，$x \le 1\,000\,001$，$N \le 2\times 10^5$。时间限制 1 秒，需要高效处理所有询问。
13
14## 解题思路
15
16由于 $x$ 最大值只有 $1\,000\,001$ 左右，而且找到下一个幸运数可能需要稍微超出 $x$ 的范围（最坏情况要找到大于 $1\,000\,001$ 的幸运数），我们可以提前预处理出所有可能的幸运数状态，然后对于每个询问直接 $O(1)$ 回答。
17
18预处理主要分为三步：
19
201. **标记超级幸运数**：枚举所有 $\ge a$ 的完全平方数，其值最大刚刚超过 $1\,000\,001$，即 $1001^2 = 1\,002\,001$。
212. **标记所有幸运数**：对于每个超级幸运数，将其所有倍数都标记为幸运数。这个过程类似于埃氏筛法。
223. **求出每个数的下一个幸运数**：从数组最大值向 $1$ 倒序遍历，记录每个数之后（或自身）的第一个幸运数。
23
24最终对于输入的 $x$，如果是幸运数就输出 `lucky`，否则直接输出预存的下一个幸运数。
25
26## 算法说明
27
28### 1. 确定预处理上限
29
30由于 $x \le 1\,000\,001$，而幸运数可能出现在 $1\,000\,001$ 之后，因此我们需要把上限设得比最大 $x$ 略大一些。$1001^2 = 1\,002\,001$ 是一个合适的超级幸运数，在上限取 $1001^2$ 的情况下，可以确保能够找到所有 $x$ 的下一个幸运数。故定义常量 `N = 1001 * 1001`。
31
32### 2. 标记幸运数
33
34```cpp
35for (int i = 1; i <= N; i++) {
36    int t = int(sqrt(i) + eps);
37    if (i >= a && t * t == i)
38        is_lucky[i] = 1;
39    if (!is_lucky[i])
40        continue;
41    for (int j = i + i; j <= N; j += i)
42        is_lucky[j] = 1;
43}

这里分两部分，但实际上是遍历 $i=1 \dots N$：

• 如果 $i$ 本身是 $\ge a$ 的完全平方数，将其标记为幸运数（它自身就是一个超级幸运数，自然是幸运数）。
• 如果 $i$ 已经被标记为幸运数（即它是某个超级幸运数或者其倍数），那么再将它的所有倍数也标记为幸运数。

由于一个数是幸运数当且仅当它是某个超级幸运数的倍数，这种递推标记能正确覆盖所有幸运数，且不会漏掉链条中的倍数。

实际上，上面这种写法等价于：先找出所有超级幸运数，再用筛法标记它们的所有倍数。

3. 预处理 next_lucky 数组

cpp
复制
1for (int i = N; i >= 1; i--)
2    next_lucky[i] = is_lucky[i] ? i : next_lucky[i + 1];

从后往前，如果当前位置 $i$ 是幸运数，那么 next_lucky[i] = i；否则，它后面第一个幸运数就是 next_lucky[i+1]。这样我们在回答询问时，对于非幸运数可以直接找到幸运化后的结果。

4. 回答询问

cpp
复制
1while (T--) {
2    int x;
3    scanf("%d", &x);
4    if (is_lucky[x])
5        cout << "lucky" << endl;
6    else
7        cout << next_lucky[x] << endl;
8}

每次询问 $O(1)$，总复杂度 $O(N + T)$，可以完美通过。

时间复杂度分析

• 寻找超级幸运数并做倍数标记：超级幸运数共有大约 $\sqrt{N}$ 个。对于每个超级幸运数 $s$，标记其倍数需要 $\frac{N}{s}$ 次操作。所有超级幸运数的标记次数总和约为 $\sum_{k \ge \lceil \sqrt{a} \rceil} \frac{N}{k^2}$。这个级数是收敛的，不超过 $N \times \frac{\pi^2}{6} \approx 1.64 N$。当 $N \approx 10^6$ 时，操作次数在 $1.6 \times 10^6$ 级别，完全可以接受。
• 预处理 next_lucky 数组复杂度 $O(N)$。
• 每次询问 $O(1)$，总询问复杂度 $O(T)$。

整体复杂度 $O(N + T)$，在 $N \le 1\,002\,001$，$T \le 2 \times 10^5$ 时能够轻松通过。

参考代码及解释

cpp
复制
1#include <cstdio>
2#include <iostream>
3#include <cmath>
4using namespace std;
5
6const int N = 1001 * 1001;          // 预处理上限，1001^2 = 1002001
7const double eps = 1e-8;            // 用于浮点误差修正
8bool is_lucky[N + 5];               // 记录每个数是否为幸运数
9int next_lucky[N + 5];              // 记录大于等于 i 的第一个幸运数
10
11int main() {
12    int a, T;
13    scanf("%d%d", &a, &T);          // 读入 a 和询问次数
14
15    // 标记所有幸运数
16    for (int i = 1; i <= N; i++) {
17        int t = int(sqrt(i) + eps);
18        // 判断 i 是否为 ≥a 的完全平方数（即超级幸运数）
19        if (i >= a && t * t == i)
20            is_lucky[i] = 1;
21        // 如果 i 本身不是幸运数，跳过倍数标记
22        if (!is_lucky[i])
23            continue;
24        // 将 i 的所有倍数标记为幸运数
25        for (int j = i + i; j <= N; j += i)
26            is_lucky[j] = 1;
27    }
28
29    // 预处理 next_lucky 数组
30    for (int i = N; i >= 1; i--)
31        next_lucky[i] = is_lucky[i] ? i : next_lucky[i + 1];
32
33    // 处理每个询问
34    while (T--) {
35        int x;
36        scanf("%d", &x);
37        if (is_lucky[x])
38            cout << "lucky" << endl;
39        else
40            cout << next_lucky[x] << endl;
41    }
42    return 0;
43}

代码说明

• N 定义为 $1001 \times 1001 = 1\,002\,001$，确保了处理 $x$ 时不会越界。
• sqrt(i) + eps 用来避免浮点数精度问题，eps = 1e-8 保证了对完全平方数的准确判断。
• 第一遍循环中，先判断 $i$ 自身是否为超级幸运数，如果是则标记；之后再用已经标记的数去标记它的倍数，这种写法巧妙地将两步合并到了一个循环中。
• next_lucky 通过倒序遍历构建，利用了后缀最优信息，使得查询时能直接找到答案。
• 最终根据 is_lucky[x] 决定输出 lucky 还是 next_lucky[x]。

本题的难点在于将幸运数的定义转化为筛法标记，并利用预处理技巧将在线询问降到 $O(1)$。理解这种 “定义→预处理→快速回答” 的模式，对解决同类问题非常有帮助。