Submission #846721

---

Source Code Expand

/*
*/
#define _CRT_SECURE_NO_WARNINGS

//#pragma comment(linker, "/STACK:16777216")
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>  
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <ctime>
#include <assert.h>

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash

#define eps 1e-10
#define M_PI 3.141592653589793
#define bs 1000000007;
#define bsize 512

const int N = 233031;

using namespace std;

int n;
int pr[N];
vector<int> primes;

map<vector<pair<long long, long long> >, int> have;
map<vector<pair<long long, long long> >, int>::iterator it;
long long ans;

vector<pair<long long, long long> > paired(vector<pair<long long, long long> > v)
{
	vector<pair<long long, long long> > res;

	for (int i = 0; i < v.size(); i++)
	{
		if (v[i].second == -1)
		{
			res.push_back(make_pair(-1, -1));
			return res;
		}
	}
	
	for (int i = 0; i < v.size(); i++)
	{
		res.push_back(v[i]);
		res[i].second = 3 - res[i].second;
		res[i].second %= 3;
	}

}

bool perf_square(long long x)
{
	long long val = sqrt(x + .5);
	return (val*val == x);
}

vector<pair<long long, long long> > parse(long long x)
{
	vector<pair<long long, long long> > res;

	for (int i = 0; i < primes.size(); i++)
	{
		if (x%primes[i])
			continue;
		int cnt = 0;
		while (x%primes[i] == 0)
		{
			cnt++;
			x /= primes[i];
		}
		if (cnt % 3 == 0)
			continue;
		res.push_back(make_pair(primes[i], cnt % 3));
	}
	if (x == 1)
		return res;
	if (perf_square(x))
	{
		int ss = sqrt(x + .5);
		res.push_back(make_pair(ss, 2));
		return res;
	}
	if (x <= 100000)
	{
		res.push_back(make_pair(x, 1));
		return res;
	}

	res.push_back(make_pair(1, -1));
	return res;
}
int main(){
	//freopen("beavers.in","r",stdin);
	//freopen("beavers.out","w",stdout);
	//freopen("F:/in.txt","r",stdin);
	//freopen("F:/output.txt","w",stdout);
	ios_base::sync_with_stdio(0);
	//cin.tie(0);

	cin >> n;

	pr[1] = 1;
	for (int i = 2; i <= 10000; i++)
	{
		if (pr[i] == 0)
		{
			for (int j = i * 2; j <= 10000; j+=i)
			{
				pr[j] = 1;
			}
		}
	}

	for (int i = 2; i <= 3000; i++)
	{
		if (pr[i] == 0)
		{
			primes.push_back(i);
		}
	}

	for (int i = 1; i <= n; i++)
	{
		long long val;
		cin >> val;
		vector<pair<long long, long long> > p = parse(val);
		/*for (int j = 0; j < p.size(); j++)
		{
			cout << p[j].first << "%" << p[j].second << endl;
		}
		cout << "!" << endl;
		*/
		have[p]++;
	}

	for (it = have.begin(); it != have.end(); it++)
	{
		int cnt = (*it).second;
		vector<pair<long long, long long> > p = (*it).first;
		vector<pair<long long, long long> > p2 = paired(p);
		if (p2 == p)
		{
			ans += 2;
			continue;
		}
		if (have.find(p2) == have.end())
		{
			ans += cnt * 2;
			continue;
		}
		ans += max(have[p2], have[p]);
	}

	cout << ans / 2 << endl;

	cin.get(); cin.get();
	return 0;
}

Submission Info

Compile Error

./Main.cpp:32:0: warning: "M_PI" redefined
 #define M_PI 3.141592653589793
 ^
In file included from /usr/include/c++/5/cmath:44:0,
                 from /usr/include/c++/5/complex:44,
                 from ./Main.cpp:9:
/usr/include/math.h:372:0: note: this is the location of the previous definition
 # define M_PI  3.14159265358979323846 /* pi */
 ^

Judge Result