简答题 偏难
#19078

小杨的幸运数 时间限制:5.0 s 内存限制:128.0 MB 问题描述 小杨认为,所有大于等于a的完全平方数都是他的超级幸运数。 小杨还认为,所有超级幸运数的…

小杨的幸运数

时间限制:5.0 s

内存限制:128.0 MB

问题描述

小杨认为,所有大于等于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

样例解释 1

1虽然是完全平方数,但它小于a,因此它并不是超级幸运数,也不是幸运数。将其进行3次+1操作后,最终得到幸运数4。

4是幸运数,因此直接输出 lucky 。

5不是幸运数,将其进行3次+1操作后,最终得到幸运数8。

9是幸运数,因此直接输出 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

数据规模

对于30%的测试点,保证a,x≤100,N≤100 。

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

对于所有测试点,保证a≤1000001;保证N≤2×105;保证1≤x≤1000001。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:python;toolbar:false">a, n = input().split() a, n = int(a), int(n) max_lucky = 1001 ** 2 + 10 is_lucky = [False for i in range(max_lucky + 1)] next_lucky = [-1 for i in range(max_lucky + 1)] for i in range(1, max_lucky): if i &gt;= a and int(i ** 0.5) ** 2 == i: is_lucky[i] = True for j in range(i + i, max_lucky, i): is_lucky[j] = True for i in range(max_lucky - 1, 0, -1): if is_lucky[i]: next_lucky[i] = i else: next_lucky[i] = next_lucky[i + 1] for i in range(n): x = int(input()) assert 1 &lt;= x &lt;= 10 ** 6 + 1 if next_lucky[x] == x: print("lucky") else: print(next_lucky[x])</pre>
这道题暂未补解析。