简答题
偏难
#21590
小杨的幸运数 时间限制:1.0 s 内存限制:128.0 MB 问题描述 小杨认为,所有大于等于 的完全平方数都是他的超级幸运数。 小杨还认为,所有超级幸运数的…
小杨的幸运数
时间限制:1.0 s
内存限制:128.0 MB
问题描述
小杨认为,所有大于等于 的完全平方数都是他的超级幸运数。
小杨还认为,所有超级幸运数的倍数都是他的幸运数。自然地,小杨的所有超级幸运数也都是幸运数。
对于一个非幸运数,小杨规定,可以将它一直+1,直到它变成一个幸运数。我们把这个过程叫做幸运化。例如,如果a=4,那么4是最小的幸运数,而1不是,但我们可以连续对1做3次+1操作,使其变为4,所以我们可以说,1幸运化后的结果是4。
现在,小杨给出N个数,请你首先判断它们是不是幸运数;接着,对于非幸运数,请你将它们幸运化。
输入描述
第一行 2 个正整数a,N。
接下来N行,每行一个正整数x,表示需要判断(幸运化)的数。
输出描述
输出N行,对于每个给定的x,如果它是幸运数,请输出 lucky ,否则请输出将其幸运化后的结果。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1
1虽然是完全平方数,但它小于a,因此它并不是超级幸运数,也不是幸运数。将其进行3次+1操作后,最终得到幸运数 。
4是幸运数,因此直接输出 lucky 。
5不是幸运数,将其进行3次+1操作后,最终得到幸运数8。
9是幸运数,因此直接输出 lucky 。
样例输入 2
样例输出 2
数据规模
对于30%的测试点,保证a,x≤100,N≤100。
对于60%的测试点,保证a,x≤106。
对于所有测试点,保证a≤1000001;保证N≤2×105;保证1≤x≤1000001。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
using namespace std;
const int N = 1001 * 1001;
const double eps = 1e-8;
bool is_lucky[N + 5];
int next_lucky[N + 5];
void init() {}
int main() {
int a, T;
scanf("%d%d", &a, &T);
for (int i = 1; i <= N; i++) {
int t = int(sqrt(i) + eps);
if (i >= a && t * t == i)
is_lucky[i] = 1;
if (!is_lucky[i])
continue;
for (int j = i + i; j <= N; j += i)
is_lucky[j] = 1;
}
for (int i = N; i; i--)
next_lucky[i] = is_lucky[i] ? i : next_lucky[i + 1];
while (T--) {
int x;
scanf("%d", &x);
if (is_lucky[x])
cout << "lucky" << endl;
else
cout << next_lucky[x] << endl;
}
return 0;
}</pre>
这道题暂未补解析。