《B3929 [GESP202312 五级] 小杨的幸运数》

题目背景对应的选择、判断题试题 - GESP 202312 C 五级 - 洛谷有题题目描述小杨认为所有大于等于 a 的完全平方数都是他的超级幸运数。小杨还认为所有超级幸运数的倍数都是他的幸运数。自然地小杨的所有超级幸运数也都是幸运数。对于一个非幸运数小杨规定可以将它一直 1直到它变成一个幸运数。我们把这个过程叫做幸运化。例如如果 a4那么 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输入 #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说明/提示样例解释 11 虽然是完全平方数但它小于 a因此它并不是超级幸运数也不是幸运数。将其进行 3 次 1 操作后最终得到幸运数 4。4 是幸运数因此直接输出lucky。5 不是幸运数将其进行 3 次 1 操作后最终得到幸运数 8。9 是幸运数因此直接输出lucky。数据规模对于 30% 的测试点保证 a,x≤100,N≤100。对于 60% 的测试点保证 a,x≤106。对于所有测试点保证 a≤1,000,000保证 N≤2×105保证 1≤x≤1,000,001。代码实现#include iostream #include vector #include cmath #include algorithm using namespace std; typedef long long ll; const int MAX 2000000; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll a; int N; cin a N; vectorbool ok(MAX 1, false); ll t_min ceil(sqrt((long double)a)); for (ll t t_min; t * t MAX; t) { ll sq t * t; for (ll mul sq; mul MAX; mul sq) { ok[mul] true; } } vectorll lucky_list; for (ll i 1; i MAX; i) { if (ok[i]) lucky_list.push_back(i); } while (N--) { ll x; cin x; auto it lower_bound(lucky_list.begin(), lucky_list.end(), x); ll res *it; if (res x) cout lucky\n; else cout res \n; } return 0; }