题目背景

对应的选择、判断题：试题 - GESP 202312 C++ 五级 - 洛谷有题

题目描述

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

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

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

现在，小杨给出 N 个数，请你首先判断它们是不是幸运数；接着，对于非幸运数，请你将它们幸运化。

输入格式

第一行 2 个正整数 a,N。

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

输出格式

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

输入输出样例

输入 #1复制

2 4 
1 
4 
5 
9

输出 #1复制

4 
lucky 
8 
lucky

输入 #2复制

16 11 
1 
2 
4 
8 
16 
32 
64 
128 
256 
512
1024

输出 #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≤100,N≤100。

对于 60% 的测试点，保证 a,x≤106。

对于所有测试点，保证 a≤1,000,000；保证 N≤2×105；保证 1≤x≤1,000,001。

代码实现：

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX = 2000000;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll a;
    int N;
    cin >> a >> N;
    
    vector<bool> ok(MAX + 1, false);
    ll t_min = ceil(sqrt((long double)a));
    for (ll t = t_min; t * t <= MAX; t++)
    {
        ll sq = t * t;
        for (ll mul = sq; mul <= MAX; mul += sq)
        {
            ok[mul] = true;
        }
    }
    vector<ll> lucky_list;
    for (ll i = 1; i <= MAX; i++)
    {
        if (ok[i]) lucky_list.push_back(i);
    }
    
    while (N--)
    {
        ll x;
        cin >> x;
        auto it = lower_bound(lucky_list.begin(), lucky_list.end(), x);
        ll res = *it;
        if (res == x)
            cout << "lucky\n";
        else
            cout << res << "\n";
    }
    return 0;
}