ABC400E题解

· · 题解

不难发现，当每个质因数的指数为偶数时，这个数一定是一个平方数。
因此 400 数一定是平方数。则从 1 到 10^{12} 中 400 数的个数最多有 10^6 个。又可以发现，所有 400 数开根号后有且仅有 2 个质因子，且开根号后范围为 [1,10^6]。因此我们可以预处理出所有 400 数开根号后的数。
现在思考怎么预处理。我们可以先记录 1 到 10^6 中所有数的质因子个数，这个可以在埃氏筛的过程中求出。然后将所有质因子数量为 2 的数平方后添加到一个数组中，这样这个数组中所有数都是 400 数。最后在这个数组中二分查找即可。

代码

#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;
}