rt。本题我的思路是首先分解出所有小于 $10^{\frac{10}{3}}$ 的质因数，并取出质因数中所有指数模 $3$ 不为 $0$ 的数以及其指数对 $3$ 取模的结果，再判断剩下的值 $s$ 是否为质数，或者为完全平方数，若是则将其所有质因数及其的指数哈希，并同时求出与其相乘为完全立方数的数的哈希结果，然而 WA 和 AC 数量几乎相等。请问这么做的正确概率是错误的吗，还是我的实现有问题。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const int MAXN = 100005;
const ull base = 131;
ll n, cnt = 0, ans = 0, prime[MAXN], sta[15], pd[MAXN]; 
ll maxn = 0, a[MAXN];
ull HASH[MAXN][2], num[15] = {8, 3, 2, 4, 5, 7, 9, 1, 6};
bool vis[MAXN];
mt19937 RAND(time(0));
map<ull, int> mp, bel;
inline ll qmi(ll a, ll b, ll MOD) {
	ll res = a % MOD, ans = 1;
	while (b) {
		if (b & 1) ans = ans * res % MOD;
		res = res * res % MOD;
		b >>= 1;
	}
	return ans;
}
inline bool millerRabin(ll n) {
    if (n < 3 || n % 2 == 0) return (n == 2);
    ll a = n - 1 , b = 0 , T = 11;
    while (a % 2 == 0) a >>= 1, b++;
    for (int i = 1; i <= T; i++) {
        ll x = 1ll * RAND() * RAND() % (n - 2) + 2 , v = qmi(x, a, n);
        if (v == 1) continue;
		int j;
        for(j = 1; j <= b; j++) {
            if (v == n - 1) break;
            v = (ll)v * v % n;
        }
        if (j > b) return false;
    }
    return true;
}
inline void euler(int maxn) {
	for (int i = 2; i <= maxn; i++) {
    	if (!vis[i]) prime[++cnt] = i;
    	for (int j = 1; j <= cnt && prime[j] <= maxn / i; j++) {
    		vis[i * prime[j]] = 1;
    		if (i % prime[j] == 0) break;
		}
	}
}
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')
		   f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	return x * f;
}
inline ll Read() {
	ll x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')
		   f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	return x * f;
}
int main() {
	srand(time(0));
	n = read();
	for (int i = 1; i <= n; i++) a[i] = Read(), maxn = max(maxn, a[i]);
	ll now = 2500;
	euler(now);
	for (int i = 1; i <= n; i++) {
		now = a[i];
		for (int j = 1; j <= cnt; j++) {
			int res = 0;
			while (now % prime[j] == 0) res++, now /= prime[j];
			res %= 3;
			if (!res) continue;
			int pos = 0, X = prime[j];
			while (X) sta[++pos] = X % 10, X /= 10;
			for (int k = 1; k <= pos; k++) HASH[i][0] = HASH[i][0] * base + num[sta[k]], HASH[i][1] = HASH[i][1] * base + num[sta[k]];
			HASH[i][0] = HASH[i][0] * base + (ull)res;
			HASH[i][1] = HASH[i][1] * base + (ull)(3 - res);
	        HASH[i][0] = HASH[i][0] * base + 10;
	        HASH[i][1] = HASH[i][1] * base + 10;
		}
		if (now == 1) continue;
		if (millerRabin(now)) {
			int pos = 0, X = now;
			while (X) sta[++pos] = X % 10, X /= 10;
			for (int k = 1; k <= pos; k++) HASH[i][0] = HASH[i][0] * base + num[sta[k]], HASH[i][1] = HASH[i][1] * base + num[sta[k]];
			HASH[i][0] = HASH[i][0] * base + 1;
			HASH[i][1] = HASH[i][1] * base + 2;
			HASH[i][0] = HASH[i][0] * base + 10;
	        HASH[i][1] = HASH[i][1] * base + 10;
	        continue;
		}
		ll l = 1, r = now, way = 1;
		while (l <= r) {
			ll mid = (l + r) >> 1;
			if (mid * mid <= now) way = max(way, mid), l = mid + 1;
			else r = mid - 1; 
		}
		if (way * way == now && millerRabin(way)) {
			int pos = 0, X = way;
			while (X) sta[++pos] = X % 10, X /= 10;
			for (int k = 1; k <= pos; k++) HASH[i][0] = HASH[i][0] * base + num[sta[k]], HASH[i][1] = HASH[i][1] * base + num[sta[k]];
			HASH[i][0] = HASH[i][0] * base + 2;
			HASH[i][1] = HASH[i][1] * base + 1;
			HASH[i][0] = HASH[i][0] * base + 10;
	        HASH[i][1] = HASH[i][1] * base + 10;
	        continue;
		}
		pd[i] = -1;
	} 
	for (int i = 1; i <= n; i++) {
		if (pd[i] == -1) continue;
		if (bel[HASH[i][0]] == 0) bel[HASH[i][0]] = i;
		mp[HASH[i][0]]++;
 	}
 	for (int i = 1; i <= n; i++) {
 		if (pd[i] == -1 || bel[HASH[i][0]] != i) continue;
 		if (HASH[i][0] == 0) {
 			ans++;
 			continue;
		 }
 		if (mp.find(HASH[i][1]) != mp.end()) {
 			ans += max(mp[HASH[i][0]], mp[HASH[i][1]]);
 			bel[HASH[i][0]] = bel[HASH[i][1]] = 0;
		}
		else ans += mp[HASH[i][0]];
	}
	printf("%lld\n", ans);
	return 0;
}