正经题解｜又又是好数

题目解析

我们可以先列举几个好数的数，4 9 25 49。
可以发现对于任意一个 $a_i$ 来说，如果它是一个完全平方数，并且 $\sqrt{a_i}$ 为一个质数，则它是好数。所以可以先用埃氏筛筛出所有 $\leq \sqrt{max_{a_i}}$ 的质数，因为只有这一半是会被用到的，最后判断这个数是不是为完全平方数即可。

AC代码

#include <bits/stdc++.h>
//#define endl '\n'
using namespace std;
typedef long long ll;
const ll R = 1e12 + 10;
ll n,a;
bitset<1000010> vis;
void init() {
    ll q = sqrt(R);
    for(ll i=2;i<=q/i;i++) {
        if (vis[i])continue;
        for(ll j=i*i;j<=q;j+=i) {
            vis[j] = true;
        }
    }
}
bool check(ll x) {
    if (x == 1)return false;
    ll q = sqrt(x);
    return q * q == x && !vis[q];
}
int main() {
    ios::sync_with_stdio(false);
    init();
    cin >> n;
    for(int i=1;i<=n;i++) {
        cin >> a;
        if (check(a))cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

复杂度

埃氏筛的复杂度为：$O(n\log\log n)$