Submission #847591

---

Source Code Expand

//In the name of Allah
#include <bits/stdc++.h>
using namespace std;

typedef long long ll; 

const int maxN = 1000 * 100 + 100; 
const int mx = 2500 + 10; 

ll a[maxN]; 
map<ll,int> cnt; 
vector<int> pr; 
int mark[maxN]; 

int main() { 
	for( int i = 2 ; i < mx ; i++ ) if( !mark[i] ) { 
		pr.push_back(i); 
		for( int j = i + i ; j < maxN ; j += i ) 
			mark[j] = true; 
	}

	ios::sync_with_stdio(false); cin.tie(0); 
	int n; cin >> n; 
	for( int i = 0 ; i < n ; i++ ) { 
		cin >> a[i]; 
		for( int t = 2 ; t < mx ; t++ ) { 
			ll z = t * 1ll * t * t; 
			while( a[i] % z == 0 ) 
				a[i] /= z; 
		}
		cnt[a[i]]++; 
	}
	sort( a , a + n ); 
	int ans = 0; 
	if( cnt[1] ) ans = 1; 
	cnt[1] = 0; 

	for( int i = 0 ; i < n ; i++ ) 
		if( cnt[a[i]] ) { 
			ll x = a[i]; 
			ll z = 1; 
			for( auto y : pr ) { 
				if( x % y == 0 ) { 
					int v = 0; 
					while( x % y == 0 ) { 
						v++; 
						x /= y;
					}
					if( v == 1 ) z *= y * 1ll * y; 
					else if( v == 2 ) z *= y; 
					if( x == 1 ) break; 
				} else if( y * 1ll * y > x ) 
					break;
			}
			if( x > 1 ) 
				z *= x * 1ll * x; 
			ans += max( cnt[a[i]] , cnt[z] ); 
			cnt[z] = 0;
			cnt[a[i]] = 0; 
			//cerr << a[i] << "   " << z << " ANS CHANGED TO " << ans << endl;
		}
	cout << ans << endl;
}

Submission Info

Judge Result