判断每个数是否幸运数;否则给出它"幸运化"(不断 +1)后的结果。
规定:
给定 N 个 x,若 x 是幸运数输出 lucky,否则输出幸运化后的结果。
筛法标记倍数后缀最近值离线预处理O(1) 查询
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 a、N;随后 N 行每行一个 x |
| 输出 | 每行 lucky 或幸运化结果 |
| 数据范围 | a ≤ 10⁶,N ≤ 2 × 10⁵,x ≤ 10⁶ + 1 |
| 超级幸运数 | 完全平方数 k² 且 ≥ a |
| 幸运数 | 超级幸运数的倍数 |
nxt[i] = lucky[i] ? i : nxt[i+1]先找出超级幸运数与幸运数。
所有 ≥ 2 的完全平方数:
2² = 4、3² = 9、4² = 16、5² = 25、…
注意 1² = 1 < 2,所以 1 不是超级幸运数
超级幸运数:4, 9, 16, 25, …
4 的倍数:4, 8, 12, 16, 20, 24, …
9 的倍数:9, 18, 27, …
16 的倍数:16, 32, …(16 已在 4 的倍数中)
合并后从小到大:4, 8, 9, 12, 16, 18, 20, …
幸运数集合已确定
| 询问 x | 是幸运数吗 | 幸运化结果 | 输出 |
|---|---|---|---|
| 1 | 否 | 不断 +1:2、3 都不是,4 是 → 4 | 4 |
| 4 | 是 | — | lucky |
| 5 | 否 | 6、7 不是,8 是 → 8 | 8 |
| 9 | 是 | — | lucky |
输出 4、lucky、8、lucky ✓
这次 a 较大,最小超级幸运数是 16。
≥ 16 的完全平方数:16, 25, 36, 49, 64, 81, 100, 121, 144, …
注意 9 = 3² < 16,所以 9 不是超级幸运数
超级幸运数:16, 25, 36, …
16 的倍数:16, 32, 48, 64, 80, 96, 112, 128, …, 1024, …
25 的倍数:25, 50, 75, 100, …
所以 1 ~ 15 里没有任何幸运数
1 ~ 15 全不是幸运数
| 询问 x | 输出 | 说明 |
|---|---|---|
| 1 | 16 | 1 ~ 15 都不是幸运数,最近的是 16 |
| 2 | 16 | 同上 |
| 4 | 16 | 4 < a=16,虽然是平方数但不合格 |
| 8 | 16 | 同上 |
| 16 | lucky | 16 是超级幸运数 |
| 32 | lucky | 32 = 16 × 2 |
| 64 | lucky | 64 = 16 × 4 |
| 128 | lucky | 128 = 16 × 8 |
| 256 | lucky | 256 = 16 × 16 |
| 512 | lucky | 512 = 16 × 32 |
| 1024 | lucky | 1024 = 16 × 64 |
输出 16、16、16、16、lucky × 7 ✓
4 这个例子:4 = 2² 确实是完全平方数,但它小于 a = 16,所以不是超级幸运数,自然也不是幸运数,要输出幸运化结果 16。这是本题最容易搞错的地方——"完全平方数"和"超级幸运数"不是一回事。标记所有幸运数,再用后缀递推求"下一个幸运数"
对每个 x 不断 +1,每次判断是否幸运数
| 方案 | 总复杂度 | 可行性 |
|---|---|---|
| 打表 + 后缀 | O(MAXV log MAXV + N) | ✅ 稳过 |
| 逐次暴力 +1 | 最坏 O(N × MAXV) | ❌ 超时 |
第一行输入 a 和 N,随后 N 行输入要判断的数。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; const int MAXV = 2100000; // 需略大于 2 × 10^6 bool lucky[MAXV + 2]; int nxt[MAXV + 2]; int main() { int a, N; scanf("%d %d", &a, &N); // 第一步:标记所有幸运数 // 超级幸运数 = 所有 k^2 且 k^2 >= a int k = 1; while ((long long)k * k < a) k++; // 找到最小的 k 使 k^2 >= a for (; (long long)k * k <= MAXV; k++) { int p = k * k; // p 是超级幸运数 for (int m = p; m <= MAXV; m += p) // p 的所有倍数也是幸运数 lucky[m] = true; } // 第二步:从后往前求"最近的下一个幸运数" nxt[MAXV + 1] = 0; // 0 表示不存在 for (int i = MAXV; i >= 1; i--) nxt[i] = lucky[i] ? i : nxt[i + 1]; // 回答询问 while (N--) { int x; scanf("%d", &x); if (lucky[x]) printf("lucky\n"); else printf("%d\n", nxt[x]); } return 0; }
while ((long long)k * k < a) k++; 在做什么?它在找最小的 k 使 k² ≥ a——这正好是最小的超级幸运数。注意用 (long long) 强制转换,因为 k * k 可能接近 int 上限。不能从 k = 1 开始标记!否则会把小于 a 的平方数(如 a=16 时的 4、9)错误地标记为超级幸运数。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
while ((long long)k*k < a) k++; | 起点 | 跳过所有小于 a 的平方数 |
for (m = p; m <= MAXV; m += p) | 标记倍数 | 超级幸运数的倍数都是幸运数 |
nxt[i] = lucky[i] ? i : nxt[i+1]; | 后缀递推 | 从后往前,一次扫描得到所有"最近幸运数" |
if (lucky[x]) | 回答 | 是则 lucky,否则输出 nxt[x] |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
2 4 | 4 lucky 8 lucky | 题面样例 1 |
16 11 | 16 16 16 16 lucky × 7 | 题面样例 2 |
1 2 | lucky lucky | a = 1 时 1 也是超级幸运数 |
4 3 | 4 4 lucky | a = 4 时 1、2、3 都要幸运化到 4 |
while (k*k < a) k++; 跳过小平方数,否则 4、9 等会被误判。一个布尔数组 + 一个整数数组,各约 2.1 × 10⁶。
✅ 预处理约几百万次操作,瞬间完成;N = 2 × 10⁵ 次询问都是 O(1)。
// "打表 + 后缀最近值"通用套路 // 第一步:标记所有满足条件的数 for (每个"基元" p) for (int m = p; m <= MAXV; m += p) good[m] = true; // 第二步:从后往前求"最近的下一个满足条件的数" nxt[MAXV + 1] = INF; for (int i = MAXV; i >= 1; i--) nxt[i] = good[i] ? i : nxt[i + 1]; // 第三步:O(1) 回答 int ans = good[x] ? x : nxt[x]; // 找"最小的 k 使 k^2 >= a" int k = 1; while ((long long)k * k < a) k++; // 或 k = ceil(sqrt(a)) // 类似的"筛法标记倍数"套路 // - 埃氏筛:标记合数 // - 本题:标记超级幸运数的倍数
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 筛法标记倍数 | 把基元的倍数全部标记 | 质数筛、倍数标记类问题 |
| 后缀最近值 | 从后往前递推 | 求"最近的下一个满足条件的数" |
| 打表 + O(1) 查询 | 用空间换时间 | 询问多、值域固定的题目 |
prv[i] = lucky[i] ? i : prv[i-1],从左往右扫一遍即可。"往前找"用前缀、"往后找"用后缀,这是同一个套路的两面。)