题目描述

小杨认为，所有大于等于 $a$ 的完全平方数都是“超级幸运数”；所有超级幸运数的倍数都是“幸运数”。给出 $N$ 个正整数 $x$，请判断它们是否为幸运数。若 $x$ 是幸运数，输出 lucky；否则不断将 $x$ 加 $1$，直到变成幸运数，并输出幸运化后的结果。

输入格式

第一行输入两个正整数 $a,N$。

接下来 $N$ 行，每行输入一个正整数 $x$。

输出格式

输出 $N$ 行。对于每个 $x$，若它已经是幸运数，输出 lucky；否则输出不小于 $x$ 的最小幸运数。

2 4
1
4
5
9

4
lucky
8
lucky

数据范围与提示

• 对于 $30\%$ 的数据，$a,x \le 100$，$N \le 10$。
• 对于 $60\%$ 的数据，$a,x \le 10^6$。
• 对于 $100\%$ 的数据，$1 \le a \le 1000001$，$1 \le x \le 1000001$，$N \le 2\times10^5$。
• 完全平方数形如 $t^2$；若 $t^2\ge a$，则 $t^2$ 及其正整数倍都是幸运数。

来源

GESP 2023年12月 C++ 五级