Submission #847442

---

Source Code Expand

#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using namespace std;
using ll=long long;

const int limit=3000;
bool isprime[limit+1];
vector<ll> prime;

void init(){
	rep(i,limit+1) isprime[i]=true;
	isprime[0]=isprime[1]=false;
	for(ll i=2;i*i<=limit;++i){
		if(isprime[i]){
			prime.push_back(i);
			for(ll j=i*i;j<=limit;j+=i)
				isprime[j]=false;
		}
	}
	return;
}

map<ll,int> cnt;

int main(void){
	init();
	const int m=prime.size();

	int n;
	cin >> n;
	rep(i,n){
		ll cur;
		cin >> cur;

		rep(j,m){
			ll cube=1LL*prime[j]*prime[j]*prime[j];
			while(cur%cube==0) cur/=cube;
		}
		cnt[cur]++;
	}

	ll ans=0LL;

	/*
	for(auto &it:cnt){
		cout << it.first << " " << it.second << " " << comp[it.first] << endl;
	}
	*/

	for(auto &it:cnt){
		if(it.first==1)
			ans+=min<ll>(1LL,it.second);
		else{
			ll tar=1LL*it.first*it.first;
			rep(j,m){
				ll cube=1LL*prime[j]*prime[j]*prime[j];
				while(tar%cube==0) tar/=cube;
			}
			ans+=max<ll>(it.second,cnt[tar]);
			it.second=0LL;
			cnt[tar]=0LL;
		}
	}
	cout << ans << endl;
	return 0;	
}

Submission Info

Judge Result