算法

(数论、筛法)

考虑将 $a$ 进行素因数分解 $a = p_1^{q_1}p_2^{q_2} \cdots p_k^{q_k}$，其中 $q_i \geqslant 2$
对于所有 $\geqslant 2$ 的 $q_i$，要拆分成 $q_i = k_1 \cdot y_1 + k_2 \cdot y_2$，其中 $k_1, k_2 \geqslant 0$ 且 $y_1, y_2 \geqslant 2$

当 $y_1$ 取 $2$，$y_2$ 取 $3$ 时可以保证所有 $\geqslant 2$ 的 $q_i$ 均有非负整数解。

• 当 $q_i \equiv 0 \pmod 3$ 时：$k_1 = 0$，$k_2 = \frac{q_i}{3}$
• 当 $q_i \equiv 1 \pmod 3$ 时：$k_1 = 2$，$k_2 = \frac{q_i-4}{3}$
• 当 $q_i \equiv 2 \pmod 3$ 时：$k_1 = 1$，$k_2 = \frac{q_i-2}{3}$

所以，原问题变成 $a$ 能否变成 $x_1^2x_2^3$

对于 $a = p_1^{q_1}p_2^{q_2} \cdots p_k^{q_k}$，只需检测每个 $q_i$ 是否 $\geqslant 2$ 即可，因为只要 $\geqslant 2$ 就可以按照对应的 $k_1, k_2$ 分配到 $x_1, x_2$ 里面

由于 $a \leqslant 10^{18}$，所以 $x_1^2x_2^3 \leqslant 10^{18}$。如果素因子 $p > 4000$，则 $p^5 \geqslant 10^{18}$。所以只需暴力判断 $4000$ 以内的素因子，对于大于 $4000$ 的 $p$，指数只可能是 $2, 3, 4$，即判断一下是否为平方数或立方数即可。

C++ 代码

#include <bits/extc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

bool check(ll x) {
    ll y = sqrt(x);
    if (y*y == x or (y+1)*(y+1) == x) return true;
    y = pow(x, 1/3.);
    if (y*y*y == x or (y+1)*(y+1)*(y+1) == x or (y+2)*(y+2)*(y+2) == x) return true;
    return false;
}

// linear sieve
vector<int> ps, pf;
void sieve(int mx) {
    pf.resize(mx + 1);
    rep(i, mx + 1) pf[i] = i;
    for (int i = 2; i <= mx; ++i) {
        if (pf[i] == i) ps.push_back(i);
        for (int j = 0; j < ps.size() and ps[j] <= pf[i]; ++j) {
            int x = ps[j] * i;
            if (x > mx) break;
            pf[x] = ps[j];
        }
    }
}

void solve() {
    ll a;
    cin >> a;

    if (check(a)) {
        puts("yes");
        return;
    }

    bool ok = true;
    rep(i, ps.size()) {
        if (a%ps[i] != 0) continue;
        int cnt = 0;
        while (a%ps[i] == 0) {
            cnt++;
            a /= ps[i];
        }
        if (cnt == 1) {
            ok = false;
            break;
        }
    }
    if (ok and check(a)) puts("yes");
    else puts("no");
}

int main() {
    sieve(4000);

    int t;
    cin >> t;

    while (t--) solve();

    return 0;
}