本题需要题解

题目大意

本题希望我们判断一个整数是否为幸运数（ $\geq a$ 的完全平方数，或为其整数倍的数），如果是，输出lucky，反之，输出大于它的最小幸运数。

算法分析

暴力思路就是在查询过程中判断是否为幸运数，如果不是，一个个往大的数找，直到找到幸运数，时间复杂度为 $O(n^2)$ ，对于 $2\cdot10^5$ 的数据肯定过不了。因此我们先想到了预处理且类似于埃氏筛，以及二分查找。其中，对于二分查找，我们可以保证数据的单调性。

正确代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5; // 数组开大一些，避免乘法时下标溢出
int a,n;
bool p[N]; // 用于存储数据i是否为幸运数
vector<int> v; // 存储每个幸运数
void init(){
    for(int i=1;i*i<=N;i++){ // 为避免精度问题，不用sqrt()
        if(i*i<a) continue; // 完全平方数小于a，跳过
        if(p[i*i]) continue; // 一个小优化，如果已经是幸运数，则其倍数不再统计
        for(int j=1;i*i*j<=N;j++) p[i*i*j]=true; // 倍数标记
    }
    for(int i=1;i<=N;i++) if(p[i]) v.push_back(i); // 有单调性，为非降序序列
}
signed main(){
    cin>>a>>n;
    init(); //预处理，类似埃氏筛
    while(n--){
        int x;cin>>x;
        if(p[x]) cout<<"lucky\n";  // 是幸运数，直接输出
        else{
            int ans=upper_bound(v.begin(),v.end(),x)-v.begin(); //二分查找函数，用于查找第一个大于某数的下标
            cout<<v[ans]<<endl;
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：预处理复杂度为 $O(N)$ ，查询复杂度为 $O(n\ logN)$ ，整体为 $O(n\ logN)$ ，可通过本题
• 空间复杂度：$O(N)$，也可接受
• 预计得分：$100pts$

注：本题ACGO数据较水，建议以洛谷为准