专栏文章

ABC400E题解

AAwsdkl
AT_abc400_e题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mippdtq4
此快照首次捕获于
2025/12/03 15:46
3 个月前
此快照最后确认于
2025/12/03 15:46
3 个月前
查看原文
不难发现，当每个质因数的指数为偶数时，这个数一定是一个平方数。
因此 400400 数一定是平方数。则从 11 到 101210^{12} 中 400400 数的个数最多有 10610^6 个。又可以发现，所有 400400 数开根号后有且仅有 22 个质因子，且开根号后范围为 [1,106][1,10^6]。因此我们可以预处理出所有 400400 数开根号后的数。
现在思考怎么预处理。我们可以先记录 11 到 10610^6 中所有数的质因子个数，这个可以在埃氏筛的过程中求出。然后将所有质因子数量为 22 的数平方后添加到一个数组中，这样这个数组中所有数都是 400400 数。最后在这个数组中二分查找即可。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int a[1000005];
vector<ll> v; //将所有 400 数存到这里

int main()
{
	for(int i = 2;i <= 1000000;i++)
	{
		if(a[i] == 0)
		{
			for(int j = i;j <= 1000000;j+=i)
			{
				a[j]++;
			}
		}
	}
	for(ll i = 2;i <= 1000000;i++)
	{
		if(a[i] == 2)
		{
			v.push_back(i*i);
		}
	}

	int T;
	scanf("%d", &T);
	while(T--)
	{
		ll n;
		scanf("%lld", &n);
		printf("%lld\n", *prev(upper_bound(v.begin(), v.end(), n)));
	}



	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...