X019 小X的幸运数
大约 4 分钟
X019 小X的幸运数
【算法】 二分查找、数学
【C++】 二分查找、lower_bound、完全平方数
【难度】 普及/提高−
X019 小X的幸运数
一、题目简述
定义"幸运数":所有 的完全平方数 (即 ),以及这些完全平方数的所有倍数。
现有 个询问,每个询问给一个数 :
- 如果 是幸运数,输出
lucky - 否则,将 不断加 1,直到变成幸运数,输出这个幸运数
数据范围:,,询问的 范围未知但不会太大。
二、解题思路
理解幸运数
以 为例:
- 大于等于 2 的完全平方数:
- 4 的倍数:
- 9 的倍数:
- 16 的倍数:
所有幸运数合在一起:
核心观察
完全平方数增长非常快。 随着 的增大迅速变大。即使 只有 ,当 超过一定值后, 本身就已经超过了合理的 范围。
假设 最大不会超过 左右(这是合理的估计,实际根据题目数据确定),我们可以预处理出这个范围内的所有幸运数。
预处理方法
- 计算起始值
- 对于 ,直到 超过上界:
- 将 的所有倍数标记为幸运数(类似筛法)
- 将所有幸运数收集到一个有序数组中
回答询问
对每个询问 :
- 使用
lower_bound找到第一个 的幸运数 - 如果这个数恰好等于 ,输出
lucky - 否则输出这个数(即大于 的最小幸运数)
上界选择
幸运数的上界需要根据题意确定。如果题目没有明确给出 的范围,我们的上界需要保证覆盖所有可能的 以及它们的"下一个幸运数"。保守估计可以取 或更大。
手动模拟
,:
- 预处理获得幸运数列表(前若干个):
- 对 二分,找到第一个 的幸运数是 8
- ,输出 8
:第一个 的幸运数是 9,恰好等于,输出 lucky。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 2e6 + 5; // 幸运数的上界
bool isLuckyNum[MAXV];
vector<int> lucky;
int main() {
int a, Q;
cin >> a >> Q;
// 生成所有幸运数(筛法)
int start = ceil(sqrt(a));
for (int k = start; k * k < MAXV; k++) {
int sq = k * k;
for (int v = sq; v < MAXV; v += sq) {
if (!isLuckyNum[v]) {
isLuckyNum[v] = true;
lucky.push_back(v);
}
}
}
sort(lucky.begin(), lucky.end());
while (Q--) {
int x;
cin >> x;
// 二分查找 >= x 的最小幸运数
auto it = lower_bound(lucky.begin(), lucky.end(), x);
if (it != lucky.end() && *it == x) {
cout << "lucky\n";
} else {
cout << *it << "\n";
}
}
return 0;
}四、复杂度分析
- 预处理:筛法生成幸运数。对于每个 ,倍数个数约为 。总标记次数约为 (调和级数的平方)。实际上由于 从 开始, 很大时倍数很少,所以预处理很快。
- 每次询问:二分查找 , 时约 。
- 总复杂度:。
- 空间复杂度:布尔数组 ,幸运数列表 。
五、知识扩展
为什么筛法不会太慢?
看起来预处理有两重循环,像是 ,但实际上:
- 内层循环的步长是 ,不是 1
- 对于 (),步长就是 100,循环次数是
- 总的循环次数
所以实际上是近似线性的,效率很高。
ceil(sqrt(a)) 的实现
在 C++ 中,可以这样计算:
int start = ceil(sqrt(a));
// 或者用整数运算:
int start = sqrt(a);
if (start * start < a) start++;后者避免了浮点数精度问题,是更推荐的做法。
上界不够大的处理
如果 的范围超过了预处理的上界 ,可以动态处理:在查询时,如果 lower_bound 返回 lucky.end()(说明当前上界内的所有幸运数都 ),则需要在线计算更大的幸运数。这在实际题目中可以通过增大 来避免。
