Submission #1499557

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, s, e) for(int i = (s); i < (e); i++)
#define FOE(i, s, e) for(int i = (s); i <= (e); i++)
#define FOD(i, s, e) for(int i = (s); i >= (e); i--)
#define ll long long

ll A[100005], prime[10005], prime_3[10005];
int n, m, x, y, z, k, w;
int p[10005];

map<ll, int> M;

void find_prime()
{
	FOE(i, 2, 10000)
	{
		if (p[i] == 1) continue;
		for (int j = i * i; j <= 10000; j += i) p[j] = 1;
	}
	
	FOE(i, 2, 10000) if (p[i] == 0) 
	{
		prime[k] = i;
		prime_3[k++] = 1ll * i * i * i;
	}
}

ll inv(ll x)
{
	ll tmp = x, ret = 1ll;
	
	FOR(i, 0, k)
	{
		if (prime_3[i] > tmp) break;
		y = 0;
		while (tmp % prime[i] == 0) 
		{
			tmp /= prime[i];
			y++;
		}
		
		if (y == 1) ret *= prime[i] * prime[i];
		else if (y == 2) ret *= prime[i];
	
		if (ret > 10000000000ll) return -1;
	}
	
	ll t = (ll)sqrt(tmp);
	if (t * t == tmp) ret *= t;
	else ret *= tmp * tmp;
	
	if (ret > 10000000000ll) return -1;
	return ret;
}

int main ()
{
	find_prime();

	scanf("%d", &n);
	FOR(i, 0, n) 
	{
		scanf("%lld", &A[i]);
		FOR(j, 0, k) while (A[i] % prime_3[j] == 0) A[i] /= prime_3[j];
	}
	
	sort(A, A + n);

	x = 0;
	FOR(i, 0, n) 
	{
		x++;
		if (i == n - 1 || A[i] != A[i + 1])
		{
			M.insert(make_pair(A[i], x));
			x = 0;
		}
	}
	
	//FOR(i, 0, n) printf("%lld ", A[i]); printf("\n");
	
	int ans = 0;
	ll tmp;
	
	FOR(i, 0, n)
	{
		if (A[i] == 1) continue;
		if (i > 0 && A[i] == A[i - 1]) continue;
		
	//	printf("%d %d\n", A[i], M.find(A[i]) -> second);
		
		tmp = inv(A[i]);
		
		if (tmp < A[i]) continue;
		if (M.find(tmp) == M.end()) ans += M.find(A[i]) -> second;
		else ans += max(M.find(A[i]) -> second, M.find(tmp) -> second);
	} 
	
	
	if (A[0] == 1) ans++;
	printf("%d\n", ans);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:61:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:64:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &A[i]);
                       ^

Judge Result