#4224. 小杨的幸运数(23-12C++五级)

小杨的幸运数(23-12C++五级)

Background

、小杨的幸运数

问题描述

⼩杨认为,所有⼤于等于a的完全平⽅数都是他的超级幸运数。 ⼩杨还认为,所有超级幸运数的倍数都是他的幸运数。⾃然地,⼩杨的所有超级 幸运数也都是幸运数。 对于⼀个⾮幸运数,⼩杨规定,可以将它⼀直+1,直到它变成⼀个幸运数。我 们把这个过程叫做幸运化。

例如

,如果a=4,那么4是最⼩的幸运数,⽽1不是, 但我们可以连续对1做3次+1操作,使其变为4,所以我们可以说, 幸运化 后的结果是 4。 现在,⼩样给出N个数,请你⾸先判断它们是不是幸运数;接着,对于⾮幸运 数,请你将它们幸运化。

输入描述

第⼀⾏ 2 个正整数a,N。 接下来 N ⾏ ,每⾏⼀个正整数x ,表⽰需要判断(幸运化) 的数。

输出描述

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

特别提醒

在常规程序中,输⼊ 、输出时提供提⽰是好习惯。但在本场考试中, 由于系统 限定,请不要在输⼊、输出中附带任何提⽰信息。

样例输入 image

样例输出

image

样例解释 1 虽然是完全平⽅数,但它⼩于a, 因此它并不是超级幸运数,也不是幸运数。 将其进⾏3次+1 操作后,最终得到幸运数 4。 4 是幸运数,因此直接输lucky。 5 不是幸运数,将其进⾏3次+1操作后,最终得到幸运数8。 9 是幸运数,因此直接输出lucky。

image

【题目大意】

本题围绕“完全平方数”这一概念,求出大于要求数字的所有全部 完全平方数作为超级幸运数字,并且根据这些完全平方数,求出范围内所有完全 平方数的倍数;再将不属于完全平方数的数字进行自增操作,直到变为最近的超 级幸运数为止。

【解题思路】

1.按要求输入数据并设定最大范围; 2.从 a 到最大数范围内进行遍历,将每个完全平方数记录到幸运数列表中;同时 当获得完全平方数后,将该数字的所有倍数记录到幸运数列表中; 3.从大到小遍历“下一个幸运数”列表,将每个非幸运数的下一个幸运数设置为 其后面的第一个幸运数; 4.最后,根据输入的整数x,如果x是幸运数,则输出 "lucky",否则输出其下一 个非幸运数。

Limitation

1s, 1024KiB for each test case.