Submission #846887

---

Source Code Expand

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	int f1=0;
	map<ll, ll> h;
	for (int i=0;i<n;i++){
		ll s;
		cin>>s;
		for (ll d=2;d*d*d<=s;d++){
			while (s%(d*d*d)==0){
				s/=(d*d*d);
			}
		}
		if (s==1){
			f1=1;
		}
		else{
			h[s]++;
		}
	}
	ll v=0;
	if (f1) v++;
	vector<ll> ps;
	for (int i=2;i<=100000;i++){
		int f=0;
		for (int p:ps){
			if (p*p>i) break;
			if (i%p==0){
				f=1;
				break;
			}
		}
		if (!f) ps.push_back(i);
	}
	for (auto t:h){
		vector<pair<ll, int> > ds;
		ll k=t.F;
		for (ll p:ps){
			while (k%p==0){
				if (ds.size()>0&&ds.back().F==p) ds.back().S++;
				else ds.push_back({p, 1});
				k/=p;
			}
			if (p*p>k) break;
		}
		if (k>1) ds.push_back({k, 1});
		ll o=1;
		for (auto d:ds){
			if (d.S==1) {
				o*=d.F*d.F;
			}
			else{
				o*=d.F;
			}
		}
		if (o>t.F){
			v+=max(h[o], h[t.F]);
		}
	}
	cout<<v<<endl;
}

Submission Info

Judge Result