自动搬运

查看原文

来自洛谷，原作者为

	what_can_I_do **

搬运于2025-08-24 21:15:59，当前版本为作者最后更新于2024-01-29 18:35:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门

最近越来越拉了。

由于 $1\le N\le 2\times 10^5$，所以考虑预处理。

首先先从大于等于 $a$ 的完全平方数开始枚举，对于每一个完全平方数，直接去枚举它的倍数，把这些数字标记起来。上限是 $1002001$，因为大于等于 $1000001$ 且离它最近的完全平方数是 $1002001$。

接下来倒着枚举所有数字，用 $la$ 记录目前最近的完全平方数。如果该数字被标记，就更改 $la$ 变为它，否则用一个数组记录比该数字大的最近的完全平方数。

询问直接判断如果该数字有被标记输出 lucky，否则输出已经记录好的比该数字大的最近的完全平方数。

CODE:

#include<bits/stdc++.h>
using namespace std;
int a,n;
int b[1002010]={0},la=1002001;
int main()
{
	scanf("%d%d",&a,&n);
	for(register int i=ceil(sqrt(a*1.0));i*i<=1002001;i++)
		for(register int j=1;j*i*i<=1002001;j++)
			b[j*i*i]=j*i*i;
	for(register int i=1002000;i>=1;i--)
		if(b[i]==i) la=i;
		else b[i]=la;
	while(n--)
	{
		int x;
		scanf("%d",&x);
		if(b[x]==x) puts("lucky");
		else printf("%d\n",b[x]);
	}
	return 0;
}