欢迎大家订阅我的专栏：算法题解：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
