GESP认证C++编程真题解析 | B3929 [GESP202312 五级] 小杨的幸运数

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：[B3929 GESP202312 五级] 小杨的幸运数 - 洛谷

【题目描述】

小杨认为，所有大于等于a aa的完全平方数都是他的超级幸运数。

小杨还认为，所有超级幸运数的倍数都是他的幸运数。自然地，小杨的所有超级幸运数也都是幸运数。

对于一个非幸运数，小杨规定，可以将它一直+ 1 +1+1，直到它变成一个幸运数。我们把这个过程叫做幸运化。例如，如果a = 4 a=4a=4，那么4 44是最小的幸运数，而1 11不是，但我们可以连续对1 11做3 33次+ 1 +1+1操作，使其变为4 44，所以我们可以说，1 11幸运化后的结果是4 44。

现在，小杨给出N NN个数，请你首先判断它们是不是幸运数；接着，对于非幸运数，请你将它们幸运化。

【输入】

第一行2 22个正整数a , N a, Na,N。

接下来N NN行，每行一个正整数x xx，表示需要判断（幸运化）的数。

【输出】

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

【输入样例】

2 4 1 4 5 9

【输出样例】

4 lucky 8 lucky

【算法标签】

《洛谷 B3929 小杨的幸运数》 #二分# #素数判断,质数,筛法# #GESP# #2023#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=1100005;// 最大范围inta,n;// a: 判断是否为完全平方数, n: 查询次数intb[N];// 存储每个数的结果intmain(){// 输入a和ncin>>a>>n;// 计算sqrt(a)的上取整intx=sqrt(a);if(x*x!=a){x++;}// 预处理：标记所有完全平方数的倍数// 从x开始，遍历所有可能的平方数for(inti=x;i*i<=1100000;i++){// 将i*i的所有倍数标记为自身for(intj=i*i;j<=1100000;j+=i*i){b[j]=j;// 标记j是某个平方数的倍数}}// 预处理：填充未标记的位置// 从后向前扫描，记录最近遇到的正数x=0;// 这里重新使用x作为临时变量for(inti=1100000;i>=0;i--){if(b[i]){x=b[i];// 更新最近遇到的标记值}else{b[i]=x;// 填充为最近的标记值}}// 调试输出，查看b数组前20个值// for (int i=1; i<=20; i++)// cout << b[i] << " ";// cout << endl;// 处理n个查询for(inti=1;i<=n;i++){intt;cin>>t;// 输入查询的数if(b[t]==t){cout<<"lucky"<<endl;// 是完全平方数的倍数}else{cout<<b[t]<<endl;// 输出最近的大于等于t的标记值}}return0;}

【运行结果】

2 4 1 4 4 lucky 5 8 9 lucky