小杨的幸运数
时间限制：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
2 4 1 4 5 9
样例输出 1
4 lucky 8 lucky
样例解释 1
1虽然是完全平方数，但它小于a，因此它并不是超级幸运数，也不是幸运数。将其进行3次+1操作后，最终得到幸运数 。
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。
相似题推荐
相等序列
时间限制： 1.0 s
内存限制：512.0 MB
题目描述
小 A 有一个包含 N 个正整数的序列A = {A1 , A2 , · · ,AN} 。小 A 每次可以花费 1 个金币执行以下任意一种操作：
选择序列中一个正整数 Ai （ 1 ≤ i ≤ N） ，将 Ai 变为 Ai * P ，P 为任意质数；
选择序列中一个正整数 Ai （ 1 ≤ i ≤ N） ，将 Ai 变为 Ai /P ，P 为任意质数，要求Ai能被p整除。
小 A 想请你帮他计算出令序列中所有整数都相同 ，最少需要花费多少金币。
输入格式
第一行一个正整数N ，含义如题面所⽰ 。
第二行包含 N 个正整数 A1 , A2 , · … ,AN ，代表序列 A。
输出格式
输出一行 ，代表最少需要花费的金币数量。
输入样例
5 10 6 35 105 42
输出样例
8
数据范围
对于60%的测试点 ，保证 1 ≤ N, Ai ≤ 100 。
对于所有测试点 ，保证 1 ≤ N, Ai ≤ 105 。
小杨要把一根长度为 L 的木头切成 K 段，使得每段长度小于等于 x 。已知每切一刀只能把一段木头分成两段，他用二分法找到满足条件的最小 x （ x 为正整数），则横线处应填写（ ）。
// 判断：在不超过 K 次切割内，是否能让每段长度 <= x
bool check(int L, int K, int x) {
int cuts = (L - 1) / x;
return cuts <= K;
}
// 二分查找最小可行的 x
int binary_cut(int L, int K) {
int l = 1, r = L;
while (l < r) {
int mid = l + (r - l) / 2;
________________________________ // 在此处填入代码
}
return l;
}
int main() {
int L = 10; // 木头长度
int K = 2; // 最多切 K 刀
cout << binary_cut(L, K) << endl;
return 0;
} A．if (check(L, K, mid)) r = mid; else l = mid + 1; |
B．if (check(L, K, mid)) r = mid+1; else l = mid + 1; |
C．if (check(L, K, mid)) r = mid + 1; else l = mid - 1; |
D．if (check(L, K, mid)) r = mid + 1; else l = mid; |
下述代码实现素数表的线性筛法，筛选出所有小于等于 的素数，则横线上应填的代码是( )。
vector<int> linear_sieve(int n) {
vector<bool> is_prime(n +1, true);
vector<int> primes;
is_prime[0] = is_prime[1] = 0; //0和1两个数特殊处理
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) {
primes.push_back(i);
}
________________________________ { // 在此处填入代码
is_prime[ i * primes[j] ] = 0;
if (i % primes[j] == 0)
break;
}
}
return primes;
}A．for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) |
B．for(int j = sqrt(n); j <= n && i * primes[j] <= n; j++) |
C．for (int j = 1; j <= sqrt(n); j++) |
D．for(int j = 1; j < n && i * primes[j] <= n; j++) |
下面给出了阶乘计算的两种方式。以下说法正确的是（ ）。
int factorial1(int n) {
if (n <= 1) return 1;
return n * factorial1(n - 1);
}
int factorial2(int n) {
int acc = 1;
while (n > 1) {
acc = n * acc;
n = n - 1;
}
return acc;
} | A． 上面两种实现方式的时间复杂度相同，都为O(n) |
B． 上面两种实现方式的空间复杂度相同，都为O(n) |
| C． 上面两种实现方式的空间复杂度相同，都为O(1) |
D． 函数 factorial1() 的时间复杂度为O(2^n)，函数 factorial2() 的时间复杂度为O(n) |
