GESP五级真题:小杨的幸运数——不会这两步,99%的人会超时

四季读书网 2026-05-03 21:05:16 1 0

GESP五级真题：小杨的幸运数——不会这两步，99%的人会超时

核心考点：筛法思想 + 二分查找
这道题表面在问「幸运数」，实际考的是你能不能把「倍数的倍数」这个关系转化为预处理打表 + 快速查询的经典模型。读完这篇，你会发现它和埃氏筛如出一辙——即使你没学过埃氏筛，看完这篇你就学会了。

📋 原题原文

题目描述

小杨认为，所有大于等于的完全平方数都是他的超级幸运数。

小杨还认为，所有超级幸运数的倍数都是他的幸运数。自然地，小杨的所有超级幸运数也都是幸运数。

对于一个非幸运数，小杨规定，可以将它一直，直到它变成一个幸运数。我们把这个过程叫做幸运化。例如，如果，那么是最小的幸运数，而不是，但我们可以连续对做次操作，使其变为，所以幸运化后的结果是。

输入格式

第一行个正整数。

接下来行，每行一个正整数，表示需要判断（幸运化）的数。

输出格式

输出行，对于每个给定的，如果它是幸运数，请输出 lucky，否则请输出将其幸运化后的结果。

数据范围

题意概括

小杨定义了一套幸运数规则。给定正整数，所有的完全平方数是超级幸运数，超级幸运数的倍数（含自身）是幸运数。

现在给出和个询问，对每个：

• 若是幸运数 → 输出 lucky
• 否则，不断直到变成幸运数 → 输出这个幸运化结果

概念解析

超级幸运数：
幸运数：
幸运化：非幸运数直至遇到幸运数，产出该幸运数

样例速览

按照输入格式，第一行给出两个数：（超级幸运数的门槛）、（共有个查询）。接下来行是每个的值：

是否幸运数	输出	说明
否		，是超级幸运数
是	`lucky`	且，本身是超级幸运数
否		，，是的倍数
是	`lucky`	，是超级幸运数

关键观察：为什么不走到而是停在？因为，是超级幸运数，所以也是幸运数。幸运化要找的是第一个的幸运数，，所以停在。

样例 2：输入第一行 16 11，即，接下来行依次为。

	是否幸运数	输出	说明
	否	全部	均小于最小超级幸运数，幸运化到
	是	全部 `lucky`	是超级幸运数，其余都是的倍数

思路分析

第一步：理解幸运数的结构

设为第一个的完全平方数，则：

• 是最小的超级幸运数，也是最小的幸运数
• 任何的数一定不是幸运数
• 幸运数 =

第二步：用筛法预处理所有幸运数

核心思想：枚举所有超级幸运数（），然后标记的所有倍数。

这和埃氏筛（Eratosthenes）的过程一模一样——只是把「质数」换成了「超级幸运数」，把「筛掉合数」换成了「标记倍数」。

for (int i = 1; i * i <= MAXV; i++) {
    int d = i * i;          // 完全平方数
    if (d < a) continue;    // 不是超级幸运数
    for (int j = 1; j * d <= MAXV; j++)
        // 标记 d 的所有倍数为幸运数
        vis[j * d] = true;
}

第三步：二分查找快速回答查询

将所有幸运数收集到一个有序数组中。对每个查询：

1. 找第一个的幸运数
2. 若 → lucky
3. 否则输出

为什么取？
因为当时，不可能 ≥ 任何超级幸运数，一定不是幸运数，结果取第一个幸运数即可（它一定）。

复杂度预估

假设，最坏为：

不到两百万次标记，次二分查找各，总耗时远小于 1 秒。

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 1002001 + 10;   // 范围略大于 x 上限 (1e6)，预留缓冲

int a, N, x;
vector<int> lucky;               // 有序的幸运数列表
bool vis[MAXV];                  // 幸运数标记数组

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a >> N;

    // 筛法：枚举完全平方数，标记其所有倍数为幸运数
    for (int i = 1; i * i <= MAXV; i++) {
        int d = i * i;
        if (d < a) continue;               // 不是超级幸运数，跳过
        for (int j = 1; j * d <= MAXV; j++)
            if (!vis[j * d]) {
                vis[j * d] = true;
                lucky.push_back(j * d);    // 记录幸运数
            }
    }

    // 排序后二分
    sort(lucky.begin(), lucky.end());

    while (N--) {
        cin >> x;
        // 第一个 ≥ max(a, x) 的幸运数
        int p = lower_bound(lucky.begin(), lucky.end(), max(a, x))
                - lucky.begin();
        // 根据题意，lucky 中一定存在 ≥ max(a, x) 的值（MAXV 已预留缓冲）
        if (lucky[p] == x)
            cout << "lucky\n";
        else
            cout << lucky[p] << '\n';
    }
    return 0;
}