Submission #848374

---

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 issq(ll x){
	ll t=sqrtl(x);
	if (t*t==x) return 1;
	if ((t-1)*(t-1)==x) return 1;
	if ((t+1)*(t+1)==x) return 1;
	return 0;
}

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<=10000;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*p>k) break;
		}
		if (k>1&&k<=1000000) {
			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});
		}
		else if(k>1){
			if (!issq(t.F)){
				v+=h[t.F];
			}
			else {
				ll ss=sqrtl(t.F);
				if (h[ss]==0) v+=h[t.F];
			}
			continue;
		}
		ll o=1;
		ld oo=1;
		for (auto d:ds){
			if (d.S==1) {
				o*=d.F*d.F;
				oo*=(ld)((ld)d.F*(ld)d.F);
			}
			else{
				o*=d.F;
				oo*=(ld)(d.F);
			}
		}
		if (oo>1e15){
			v+=h[t.F];
		}
		else if (o>t.F){
			v+=max(h[o], h[t.F]);
		}
		else{
			if (h[o]==0) v+=h[t.F];
		}
	}
	cout<<v<<endl;
}

Submission Info

Judge Result