Blog
题目
思路
代码
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#define int long long
using namespace std;
const int N = 100010;
int n, A[N], B[N], C[N];
int cnt, p[N], st[N];
void init(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) p[++cnt] = i;
for (int j = 1; p[j] <= n / i; j++) {
st[p[j] * i] = true;
if (i % p[j] == 0) break;
}
}
}
map<int, int> to;
signed main() {
init(5000); // 5000 * 5000 * 5000 > 1e10;
cin >> n;
int res = 0;
for (int i = 1, b; i <= n && cin >> b; i++) {
int a = 1, c = 1;
for (int j = 1; j <= cnt; j++) {
int k = 0;
while (b % p[j] == 0) b /= p[j], k++;
k %= 3;
if (!k) continue; // 如果 k = 0, 下面c不用乘
for (int u = 1; u <= k; u++) a = a * p[j];
for (int u = k + 1; u <= 3; u++) c = c * p[j];
}
a *= b; // 别忘了还有剩下的
if (b <= 1e5) c *= b * b;
else if (b >= 1e5 && (int)sqrt(b) * (int)sqrt(b) == b) c *= sqrt(b);
else c = -1; // 如果都不满足, 那就防止错误的c对答案产生影响
A[i] = a, C[i] = c, to[a]++; // 发现不用记录 b
}
for (int i = 1; i <= n; i++) {
if (A[i] == 1) continue;
res += max(to[A[i]], to[C[i]]);
to[A[i]] = to[C[i]] = 0;
}
if (to[1]) res++;
cout << res << endl;
return 0;
}