Submission #1301747

---

Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
long long n, s[100000], t[100000], K, ret, inf = (1LL << 40), num[2];
vector<pair<long long, int>>vec[3200000]; bool used[100000]; vector<bool>vec2[3200000];
long long solve(long long I) {
	long long ret = 1;
	for (long long i = 2; i*i*i <= s[i]; i++) {
		long long U = 0; while (I%i == 0) { I /= i; U++; U %= 3; }
		for (int j = 0; j < (3 - U % 3) % 3; j++) {
			if (ret*i <= inf)ret *= i;
			else ret = inf;
		}
	}
	long long G = (1.0L*sqrtl(1.0L*I) + 0.5L); if (G*G == I) { ret *= G; }
	else { for (int i = 0; i < 2; i++) { if ((inf / I) >= ret)ret *= I; else ret = inf; } }
	return min(ret, inf);
}
void dfs(int pos, int depth) {
	if (used[pos] == true)return;
	num[depth]++; used[pos] = true;
	for (int i = 1; i <= 2000; i++) {
		long long P = 1LL * i*i*i*t[pos]; if (P > 10000000000LL)break;
		int B = (P >> 12); if (vec[B].size() == 0)continue;
		
		int pos1 = lower_bound(vec[B].begin(), vec[B].end(), make_pair(P, 0)) - vec[B].begin();
		if (pos1 >= vec[B].size() || vec[B][pos1].first != P || vec2[B][pos1] == true)continue;
		vec2[B][pos1] = true;
		while (pos1 < vec[B].size() && vec[B][pos1].first == P) {
			dfs(vec[B][pos1].second, depth ^ 1); pos1++;
		}
	}
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s[i]; t[i] = solve(s[i]);
		if (t[i] != 1)vec[s[i] >> 12].push_back(make_pair(s[i], i)); else K = 1;
	}
	for (int i = 0; i < 3200000; i++) { sort(vec[i].begin(), vec[i].end()); vec2[i].resize(vec[i].size()); }
	for (int i = 0; i < n; i++) {
		if (t[i] == 1 || used[i] == true)continue;
		num[0] = 0; num[1] = 0;
		dfs(i, 0); ret += max(num[0], num[1]);
	}
	cout << ret + K << endl;
	return 0;
}

Submission Info

Judge Result