G5003 [GESP202312 五级] 小杨的幸运数 题解

知识点：数论、筛法、预处理。

解题思路

筛出所有不小于a的完全平方数的倍数作为幸运数，再从大到小预处理每个位置右侧最近幸运数。查询幸运数自身时输出lucky，否则输出下一幸运数。

为什么正确

标记覆盖定义允许的每个平方因子倍数，逆向扫描的last始终是当前点右侧最近合法数。

易错点

只使用平方数≥a的因子；预处理上界需覆盖查询后的下一个幸运数，本代码按题目上限设置M=2001000。

复杂度

设筛界M，预处理O(M log M)保守上界，单次查询O(1)，空间O(M)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a,n;
    cin>>a>>n;
    const int M=2001000;
    vector<int>nxt(M+1);
    for(int i=1;i*i<=M;i++)if(i*i>=a)for(int j=i*i;j<=M;j+=i*i)nxt[j]=j;
    int last=M;
    for(int i=M;i>=1;i--) {
        if(nxt[i])last=i;
        else nxt[i]=last;
    }
    while(n--) {
        int x;
        cin>>x;
        if(nxt[x]==x)cout<<"lucky\n";
        else cout<<nxt[x]<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。