Submission #846480

---

Source Code Expand

#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N;
	cin >> N;
	vector<int> P;
	for(int i =2; i <= 2200; i++) {
		bool isP =true;
		for(int j =2; j < i; j++) if(i%j == 0) isP =false;
		if(isP) P.push_back(i);}
//	cout << P.size() << "\n";
	map< pair<long long,long long>,int> M;
	for(int i =0; i < N; i++) {
		long long x;
		cin >> x;
		long long y =x, z =1;
		ALL_THE(P,it) {
			if(*it > x) break;
			if(x%(*it) != 0) continue;
			long long a =1LL*(*it)*(*it)*(*it);
			while(x%a == 0) {
				x /=a;
				y /=a;}
			int pa =0;
			while(x%(*it) == 0) {x /=*it; pa++;}
			if(pa == 2) z *=(*it);
			if(pa == 1) z *=1LL*(*it)*(*it);
			z =min(z,1LL<<35);}
		if(x > 1) {
			long long s =sqrt(x);
			while(s > 0 && s*s > x) s--;
			while(s*s < x) s++;
			if(s*s == x) z *=s;
			else z *=x*x;}
		z =min(z,1LL<<35);
		M[make_pair(y,z)]++;}
	int ans =0;
	if(M[make_pair(1LL,1LL)] > 0) ans++;
	ALL_THE(M,it) if(it->ff.ff > 0) {
		auto jt =M.find(make_pair(it->ff.ss,it->ff.ff));
		if(jt == M.end()) ans +=it->ss;
		else if(it->ff.ff > it->ff.ss) ans +=max(it->ss,jt->ss);
		}
	cout << ans << "\n";
	return 0;}

// look at my code
// my code is amazing

Submission Info

Judge Result