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

· · 题解

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

这题运用了埃氏筛的思想，标记完全平方数及其倍数。

上代码：

#include<bits/stdc++.h>
using namespace std;
int f[1111111],HHH=1001*1001;
int main()
{
    int a,n;
    cin>>a>>n;
    for(int i=a;i<=HHH;i++) if(int(sqrt(i))*int(sqrt(i))==i) for(int j=i;j<=HHH;j+=i) f[j]=1;//筛
    while(n--)
    {
        int x;
        cin>>x;
        if(f[x]) puts("lucky");//如果本身就是幸运数直接输出lucky
        else
        {
            while(!f[x]) x++;//自增，直到成为幸运数
            cout<<x<<endl;//输出最少次自增所得的幸运数
        }
    }
    return 0;
}

AC 记录