Problem:


Score : 1100 points

Problem Statement

Snuke got positive integers s_1,...,s_N from his mother, as a birthday present. There may be duplicate elements.

He will circle some of these N integers. Since he dislikes cubic numbers, he wants to ensure that if both s_i and s_j (i ≠ j) are circled, the product s_is_j is not cubic. For example, when s_1=1,s_2=1,s_3=2,s_4=4, it is not possible to circle both s_1 and s_2 at the same time. It is not possible to circle both s_3 and s_4 at the same time, either.

Find the maximum number of integers that Snuke can circle.

Constraints

1 ≦ N ≦ 10^5

1 ≦ s_i ≦ 10^{10}

All input values are integers.

Input

The input is given from Standard Input in the following format:

N
s_1
:
s_N

Output

Print the maximum number of integers that Snuke can circle.

Sample Input 1

8
1
2
3
4
5
6
7
8

Sample Output 1

6

Snuke can circle 1,2,3,5,6,7.

Sample Input 2

6
2
4
8
16
32
64

Sample Output 2

3

Sample Input 3

10
1
10
100
1000000007
10000000000
1000000009
999999999
999
999
999

Sample Output 3

9



Sample input:
8
1
2
3
4
5
6
7
8


Sample output:
6

Submission status: Wrong Answer

Solution code:
import sys
from subprocess import Popen, PIPE
from itertools import groupby
from collections import Counter

def main():
    sys.stdin.readline()
    S = sys.stdin.read().split()
    T = []
    inv_dict = {}
    Factors = Popen(["factor"] + S, stdout=PIPE).communicate()[0].split(b"\n")
    for factors in Factors:
        factors = map(int, factors.split()[1:])
        t = 1
        t_inv = 1
        for f, group in groupby(factors):
            n = len(list(group)) % 3
            if n == 1:
                t *= f
            elif n == 2:
                t_inv *= f
        t, t_inv = t * t_inv * t_inv, t * t * t_inv
        T.append(t)
        inv_dict[t] = t_inv

    counter_T = Counter(T)
    ans = 0
    for t, t_cnt in counter_T.items():
        if t == 1:
            ans += 1
            continue
        t_inv = inv_dict[t]
        t_inv_cnt = counter_T[t_inv]
        if t_cnt > t_inv_cnt or (t_cnt == t_inv_cnt and t > t_inv):
            ans += t_cnt
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

def make_prime_checker(n):
    # nまでの自然数が素数かどうかを表すリストを返す  O(nloglogn)
    is_prime = [False, True, False, False, False, True] * (n//6+1)
    del is_prime[n+1:]
    is_prime[1:4] = False, True, True
    for i in range(5, int(n**0.5)+1):
        if is_prime[i]:
            is_prime[i*i::i] = [False] * (n//i-i+1)
    return is_prime

def main():
    Primes = [p for p, is_p in enumerate(make_prime_checker(2200)) if is_p]
    def decomp(n):
        res1 = res2 = 1
        for p in Primes:
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            cnt %= 3
            if cnt == 1:
                res1 *= p
            elif cnt == 2:
                res2 *= p
        res1 *= n
        return res1 * res2 * res2, res1 * res1 * res2

    N, *S = map(int, sys.stdin.read().split())
    T = []
    inv_dict = {}
    for s in S:
        t, t_inv = decomp(s)
        T.append(t)
        inv_dict[t] = t_inv

    counter_T = Counter(T)
    ans = 0
    for t, t_cnt in counter_T.items():
        if t == 1:
            ans += 1
            continue
        t_inv = inv_dict[t]
        t_inv_cnt = counter_T[t_inv]
        if t_cnt > t_inv_cnt or (t_cnt == t_inv_cnt and t > t_inv):
            ans += t_cnt
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline


def make_prime_numbers(n):
    """n以下の素数を列挙したリストを出力する
    計算量: O(NloglogN)
    入出力例: 30 -> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    """
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(2 * i, n + 1, i):
            is_prime[j] = False
    prime_numbers = [i for i in range(n + 1) if is_prime[i]]
    return prime_numbers


n = int(input())
s = [int(input()) for i in range(n)]


primes = make_prime_numbers(int((10 ** 10) ** (1 / 3) + 20))
pow2 = set([i ** 2 for i in range(10 ** 5 + 10)])
to_anti = {}

# s[i] が立方数で割り切れるときは割る
for i in range(n):
    anti = 1
    tmp_s = s[i]
    for div in primes:
        cnt = 0
        while tmp_s % div == 0:
            tmp_s //= div
            cnt += 1
        mod_cnt = cnt % 3
        cnt = cnt - mod_cnt
        s[i] //= (div ** cnt)
        anti *= div ** ((3 - mod_cnt) % 3)
    if tmp_s in pow2:
        to_anti[s[i]] = anti * tmp_s
    else:
        to_anti[s[i]] = anti * (tmp_s ** 2)

# key: s[i], val: 個数
cnts = {}
for key in s:
    if key not in cnts:
        cnts[key] = 0
    cnts[key] += 1

# 例えば、key = (2 ** 2) * (5 ** 1) と key = (2 ** 1) * (5 ** 2) は
# 片方しか選べないので、 cnts[key]が大きい方を選ぶと得する
ans = 0
used = set([])
for key in cnts:
    if key == 1:
        ans += 1
        continue
    if key in used:
        continue
    anti_key = to_anti[key]
    used.add(anti_key)
    if anti_key in cnts:
        ans += max(cnts[anti_key], cnts[key])
    else:
        ans += cnts[key]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline


def make_prime_numbers(n):
    """n以下の素数を列挙したリストを出力する
    計算量: O(NloglogN)
    入出力例: 30 -> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    """
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(2 * i, n + 1, i):
            is_prime[j] = False
    prime_numbers = [i for i in range(n + 1) if is_prime[i]]
    return prime_numbers


n = int(input())
s = [int(input()) for i in range(n)]


primes = make_prime_numbers(int((10 ** 10) ** (1 / 3) + 20))
to_anti = {}

# s[i] が立方数で割り切れるときは割る
for i in range(n):
    anti = 1
    tmp_s = s[i]
    for div in primes:
        cnt = 0
        while tmp_s % div == 0:
            tmp_s //= div
            cnt += 1
        mod_cnt = cnt % 3
        cnt = cnt - mod_cnt
        s[i] //= (div ** cnt)
        anti *= div ** ((3 - mod_cnt) % 3)
    if tmp_s ** 0.5 == int(tmp_s ** 0.5):
        to_anti[s[i]] = anti * tmp_s
    else:
        to_anti[s[i]] = anti * (tmp_s ** 2)

# key: s[i], val: 個数
cnts = {}
for key in s:
    if key not in cnts:
        cnts[key] = 0
    cnts[key] += 1

# 例えば、key = (2 ** 2) * (5 ** 1) と key = (2 ** 1) * (5 ** 2) は
# 片方しか選べないので、 cnts[key]が大きい方を選ぶと得する
ans = 0
used = set([])
for key in cnts:
    if key == 1:
        ans += 1
        continue
    if key in used:
        continue
    anti_key = to_anti[key]
    used.add(anti_key)
    if anti_key in cnts:
        ans += max(cnts[anti_key], cnts[key])
    else:
        ans += cnts[key]

print(ans)

Submission status: Wrong Answer

Solution code:
def make_prime_numbers(n):
    """n以下の素数を列挙したリストを出力する
    計算量: O(NloglogN)
    入出力例: 30 -> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    """
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(2 * i, n + 1, i):
            is_prime[j] = False
    prime_numbers = [i for i in range(n + 1) if is_prime[i]]
    return prime_numbers


n = int(input())
s = [int(input()) for i in range(n)]


primes = make_prime_numbers(10 ** 4)
to_anti = {}

# s[i] が立方数で割り切れるときは割る
for i in range(n):
    anti = 1
    tmp_s = s[i]
    for div in primes:
        cnt = 0
        while tmp_s % div == 0:
            tmp_s //= div
            cnt += 1
        mod_cnt = cnt % 3
        cnt = cnt - mod_cnt
        s[i] //= (div ** cnt)
        anti *= div ** ((3 - mod_cnt) % 3)
    if tmp_s ** 0.5 == int(tmp_s ** 0.5):
        to_anti[s[i]] = anti * tmp_s
    else:
        to_anti[s[i]] = anti * (tmp_s ** 2)

# key: s[i], val: 個数
cnts = {}
for key in s:
    if key not in cnts:
        cnts[key] = 0
    cnts[key] += 1

# 例えば、key = (2 ** 2) * (5 ** 1) と key = (2 ** 1) * (5 ** 2) は
# 片方しか選べないので、 cnts[key]が大きい方を選ぶと得する
ans = 0
used = set([])
for key in cnts:
    if key == 1:
        ans += 1
        continue
    if key in used:
        continue
    anti_key = to_anti[key]
    used.add(anti_key)
    if anti_key in cnts:
        ans += max(cnts[anti_key], cnts[key])
    else:
        ans += cnts[key]

print(ans)

Submission status: Wrong Answer

Solution code:
def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

prime=get_sieve_of_eratosthenes_new(2160)

def ind(b,n):
    res=0
    while n%b==0:
        res+=1
        n//=b
    return res

import sys

input=sys.stdin.readline

N=int(input())
dic={}
inverse={}
for i in range(N):
    s=int(input())
    S=s**2
    for p in prime:
        a=ind(p,s)
        s//=p**(a-a%3)
        S//=p**(2*a-(2*a)%3)
    if s not in dic:
        dic[s]=0
        inverse[s]=0
    dic[s]+=1
    inverse[s]=S

one=0
double=0
for i in dic:
    if i!=1:
        if inverse[i] in dic:
            double+=max(dic[i],dic[inverse[i]])
        else:
            one+=dic[i]

double//=2
ans=one+double
if 1 in dic:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
nmax = 10**5+10
eratos = [0 for i in range(nmax+1)]
prime = []
cnt = 2
while True:
  while cnt <= nmax and eratos[cnt]:
    cnt += 1
  if cnt > nmax:
    break
  eratos[cnt] = 1
  prime.append(cnt)
  for i in range(cnt**2,nmax+1,cnt):
    eratos[i] = 1
cbls = []
sqst = set()
for i in prime:
  if i**3 <= 10**10:
    cbls.append(i**3)
  else:
    sqst.add(i**2)
n = int(input())
a = [int(input()) for i in range(n)]
dc = defaultdict(int)
for i in a:
  for p in cbls:
    while i%p == 0:
      i //= p
  dc[i] += 1
ans = n
for i,v in dc.items():
  if i == 1:
    ans -= v-1
    continue
  if v == 0:
    continue
  x = 1
  for p in prime:
    if p**3 > 10**10:
      break
    if i%(p*p) == 0:
      x *= p
      i //= p*p
    elif i%p == 0:
      x *= p**2
      i //= p
  if i in sqst:
    x *= int(i**0.5+0.5)
  if x == 1:
    x = i**2
  if x in dc:
    ans -= min(dc[x],v)
    dc[x] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
nmax = 10**5+10
eratos = [0 for i in range(nmax+1)]
prime = []
cnt = 2
while True:
  while cnt <= nmax and eratos[cnt]:
    cnt += 1
  if cnt > nmax:
    break
  eratos[cnt] = 1
  prime.append(cnt)
  for i in range(cnt**2,nmax+1,cnt):
    eratos[i] = 1
cbls = []
sqst = set()
for i in prime:
  if i**3 <= 10**10:
    cbls.append(i**3)
  else:
    sqst.add(i**2)
n = int(input())
a = [int(input()) for i in range(n)]
dc = defaultdict(int)
for i in a:
  for p in cbls:
    while i%p == 0:
      i //= p
  dc[i] += 1
ans = n
for i,v in dc.items():
  if i == 1:
    ans -= v-1
    continue
  if v == 0:
    continue
  x = 1
  for p in prime:
    if p**3 > 10**10:
      break
    if i%(p*p) == 0:
      x *= p
      i //= p*p
    elif i%p == 0:
      x *= p**2
      i //= p
  if i in sqst:
    x *= int(i**0.5+0.5)
  if x == 1:
    continue
  if x in dc:
    ans -= min(dc[x],v)
    dc[x] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
nmax = 10**5+10
eratos = [0 for i in range(nmax+1)]
prime = []
cnt = 2
while True:
  while cnt <= nmax and eratos[cnt]:
    cnt += 1
  if cnt > nmax:
    break
  eratos[cnt] = 1
  prime.append(cnt)
  for i in range(cnt**2,nmax+1,cnt):
    eratos[i] = 1
cbls = []
sqst = set()
for i in prime:
  if i**3 <= 10**10:
    cbls.append(i**3)
  else:
    sqst.add(i**2)
n = int(input())
a = [int(input()) for i in range(n)]
dc = defaultdict(int)
for i in a:
  for p in cbls:
    while i%p == 0:
      i //= p
  dc[i] += 1
ans = n
for i,v in dc.items():
  if i == 1:
    ans -= v-1
    continue
  if v == 0:
    continue
  if i in sqst:
    x = int(i**0.5+0.5)
  else:
    x = 1
    for p in prime:
      if p**3 > 10**10:
        break
      if i%(p*p) == 0:
        x *= p
      elif i%p == 0:
        x *= p**2
    if x == 1:
      continue
  if x in dc:
    ans -= min(dc[x],v)
    dc[x] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
nmax = 10**5+10
eratos = [0 for i in range(nmax+1)]
prime = []
cnt = 2
while True:
  while cnt <= nmax and eratos[cnt]:
    cnt += 1
  if cnt > nmax:
    break
  eratos[cnt] = 1
  prime.append(cnt)
  for i in range(cnt**2,nmax+1,cnt):
    eratos[i] = 1
cbls = []
sqst = set()
for i in prime:
  if i**3 <= 10**10:
    cbls.append(i**3)
  else:
    sqst.add(i**2)
n = int(input())
a = [int(input()) for i in range(n)]
dc = defaultdict(int)
for i in a:
  for p in cbls:
    while i%p == 0:
      i //= p
  dc[i] += 1
ans = n
for i,v in dc.items():
  if i == 1:
    ans -= v-1
    continue
  if v == 0:
    continue
  if i in sqst:
    x = int(i**0.5+0.5)
  else:
    x = 1
    for p in prime:
      if p**3 > 10**10:
        break
      if i%(p*p) == 0:
        x *= p
        i //= p*p
      elif i%p == 0:
        x *= p**2
        i //= p
    if x == 1:
      continue
  if x in dc:
    ans -= min(dc[x],v)
    dc[x] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def prime_sieve(end):
    assert end > 1
    is_prime = [True for i in range(end)]
    is_prime[0], is_prime[1] = False, False
    primes = list()
    for i in range(2,end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes

def prime_factorize(n,primes):
  res = []
  for i in primes:
    tmp = 0
    while not (n%i):
      n //= i
      tmp += 1
    res.append(tmp%3)
  res.append(n)
  return tuple(res)


n = int(input())
s = [int(input()) for i in range(n)]
primes = prime_sieve(int(max(s) ** (0.25))+2)
len_primes = len(primes)
factorized = defaultdict(int)
square = dict()
for i in range(1,100001):
  square[i**2] = i
cubic = set([i**3 for i in range(1,4000)])
for i in s:
  t = prime_factorize(i,primes)
  factorized[t] += 1
ans = n
f = factorized.items()
for k,v in f:
  rem = k[-1]
  another = [(3-i) % 3 for i in k[:-1]]
  if rem in cubic:
    another.append(1)
  elif rem in square:
    another.append(square[rem])
  else:
    another.append(rem**2)
  another = tuple(another)
  if k == another:
    ans -= factorized[k] - 1
    continue
  if another in factorized:
    if factorized[k] <= factorized[another]:
      ans -= factorized[k]
      factorized[k] = 0
    else:
      ans -= factorized[another]
      factorized[another] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import copy

def prime_sieve(end):
    assert end > 1
    is_prime = [True for i in range(end)]
    is_prime[0], is_prime[1] = False, False
    primes = list()
    for i in range(2,end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes #リスト型

def prime_factorize(n,primes):
  res = []
  for i in primes:
    tmp = 0
    while not (n%i):
      n //= i
      tmp += 1
    res.append(tmp%3)
  res.append(n)
  return tuple(res)


n = int(input())
s = [int(input()) for i in range(n)]
primes = prime_sieve(int(max(s) ** (0.25))+2)
len_primes = len(primes)
factorized = defaultdict(int)
square = dict()
for i in range(1,100001):
  square[i**2] = i
cubic = set([i**3 for i in range(1,4000)])
for i in s:
  t = prime_factorize(i,primes)
  factorized[t] += 1
ans = n
f = factorized.copy().items()
for k,v in f:
  rem = k[-1]
  another = [(3-i) % 3 for i in k[:-1]]
  if rem in cubic:
    another.append(1)
  elif rem in square:
    another.append(square[rem])
  else:
    another.append(rem**2)
  another = tuple(another)
  if k == another:
    ans -= factorized[k] - 1
    continue
  if factorized[k] <= factorized[another]:
    ans -= factorized[k]
    factorized[k] = 0
  else:
    ans -= factorized[another]
    factorized[another] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
def eratosthenes(n):
    isp = [True] * (n + 1)
    for i in range(2, n):
        if i * i > n:
            break
        if isp[i]:
            for i in range(i * 2, n + 1, i):
                isp[i] = False
    return [i for i in range(2, n + 1) if isp[i]]

MAX = 10 ** 10 + 10
MAX2 = int(MAX ** (1 / 2))
MAX3 = int(MAX ** (1 / 3))
prime = eratosthenes(MAX3)
cubic = [i ** 3 for i in range(MAX2)]

def normalize(n):
    for p in prime:
        while n % cubic[p] == 0:
            n //= cubic[p]
    return n

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]

    res = 0
    mp = dict()

    for j, i in enumerate(A):
        i_norm = normalize(i)
        if i_norm == 1:
            res += 1
        else:
            if i_norm in mp:
                mp[i_norm] += 1
            else:
                mp[i_norm] = 1
    
    if res > 0:
        res = 1
    
    st = set()
    for k, v in mp.items():
        if k in st:
            continue
        st.add(k)
        k_rev = normalize(k ** 2)
        if k_rev in mp:
            res += max(v, mp[k_rev])
            st.add(k_rev)
        else:
            res += v
    
    print(res)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    if "W" in S and not "E" in S:
        print("No")
    elif "E" in S and not "W" in S:
        print("No")
    elif "N" in S and not "S" in S:
        print("No")
    elif "S" in S and not "N" in S:
        print("No")
    else:
        print("Yes")
    return

def examB():
    N = I()
    A = [I()for _ in range(N)]
    ans = 0
    for i in range(N-1):
        ans += A[i]//2
        if A[i]%2 and A[i+1]>=1:
            ans += 1
            A[i+1] -= 1
    ans += A[N-1]//2
    print(ans)
    return

def examC():
    N = I()
    A = [I()for _ in range(N)]
    if N==1:
        print(0)
        return
    odd = set()
    for i in range(N):
        if i&1==0:
            odd.add(A[i])
    A.sort()
    ans = 0
    for i in range((N+1)//2):
        if A[i*2] in odd:
            continue
        ans += 1
    print(ans)
    return

def examD():
    def factorization_(a):
        rep = [[]for _ in range(2)]
        pair = []
        for i in range(2,int(10**(0.34))+2):
            cur = 0
            while a%i==0:
                cur += 1
                a //= i
            if cur>0:
                cur %= 3
                if cur==0:
                    continue
                rep[0].append((i,cur))
                pair.append((i,3-cur))
        if not rep[0]:
            rep[0].append((0,0))
            pair.append((0,0))
        rep[1] = a
        rep[0] = tuple(rep[0])

        rep = tuple(rep)
        pair = tuple(pair)
        return rep, pair

    def square(a):
        rep = set()
        for i in range(int(10**(0.33)),a+1):
            rep.add(i**2)
        return rep

    N = I()
    S = [I()for _ in range(N)]
    group = defaultdict(int)
    P = defaultdict(tuple)
    for s in S:
        g,p = factorization_(s)
        group[g] += 1
        P[g[0]] = p
    #print(group)
    G2 = deepcopy(group)
    #print(P)
    sq = square(int(10**(5))+1)
    used = set()
    ans = 0
    for key,c in group.items():
        rep, rest = key
        if (rep,rest) in used:
            continue

        if rest in sq:
            pair = int(pow((rest+1),0.5))
        else:
            pair = rest**2
        if rep==((0,0),) and pair==1:
            ans += 1
        else:
            if c<G2[(P[rep],pair)]:
                ans += G2[(P[rep],pair)]
            else:
                ans += c
        used.add((P[rep], pair))
        #print(ans)
    print(ans)
    #print(used)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    if "W" in S and not "E" in S:
        print("No")
    elif "E" in S and not "W" in S:
        print("No")
    elif "N" in S and not "S" in S:
        print("No")
    elif "S" in S and not "N" in S:
        print("No")
    else:
        print("Yes")
    return

def examB():
    N = I()
    A = [I()for _ in range(N)]
    ans = 0
    for i in range(N-1):
        ans += A[i]//2
        if A[i]%2 and A[i+1]>=1:
            ans += 1
            A[i+1] -= 1
    ans += A[N-1]//2
    print(ans)
    return

def examC():
    N = I()
    A = [I()for _ in range(N)]
    if N==1:
        print(0)
        return
    odd = set()
    for i in range(N):
        if i&1==0:
            odd.add(A[i])
    A.sort()
    ans = 0
    for i in range((N+1)//2):
        if A[i*2] in odd:
            continue
        ans += 1
    print(ans)
    return

def examD():
    def factorization_(a):
        rep = [[]for _ in range(2)]
        pair = []
        for i in range(2,int(10**(10*1/3))+2):
            cur = 0
            while a%i==0:
                cur += 1
                a //= i
            if cur>0:
                cur %= 3
                if cur==0:
                    continue
                rep[0].append((i,cur))
                pair.append((i,3-cur))
        if not rep[0]:
            rep[0].append((0,0))
        rep[1] = a
        rep[0] = tuple(rep[0])

        rep = tuple(rep)
        pair = tuple(pair)
        return rep, pair

    def square(a):
        rep = set()
        for i in range(2,a+1):
            rep.add(i**2)
        return rep

    N = I()
    S = [I()for _ in range(N)]
    group = defaultdict(int)
    P = defaultdict(tuple)
    for s in S:
        g,p = factorization_(s)
        group[g] += 1
        P[g[0]] = p
    #print(group)
    G2 = deepcopy(group)
    #print(P)
    sq = square(int(10**(5))+1)
    used = set()
    ans = 0
    for key,c in group.items():
        rep, rest = key
        if (rep,rest) in used:
            continue
        if rest in sq:
            pair = int(pow((rest+1),0.5))
        else:
            pair = rest**2
        if rep==((0,0),) and rest==1:
            ans += 1
        else:
            if c<G2[(P[rep],pair)]:
                ans += G2[(P[rep],pair)]
            else:
                ans += c
        used.add((P[rep], pair))
        #print(ans)
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    if "W" in S and not "E" in S:
        print("No")
    elif "E" in S and not "W" in S:
        print("No")
    elif "N" in S and not "S" in S:
        print("No")
    elif "S" in S and not "N" in S:
        print("No")
    else:
        print("Yes")
    return

def examB():
    N = I()
    A = [I()for _ in range(N)]
    ans = 0
    for i in range(N-1):
        ans += A[i]//2
        if A[i]%2 and A[i+1]>=1:
            ans += 1
            A[i+1] -= 1
    ans += A[N-1]//2
    print(ans)
    return

def examC():
    N = I()
    A = [I()for _ in range(N)]
    if N==1:
        print(0)
        return
    odd = set()
    for i in range(N):
        if i&1==0:
            odd.add(A[i])
    A.sort()
    ans = 0
    for i in range((N+1)//2):
        if A[i*2] in odd:
            continue
        ans += 1
    print(ans)
    return

def examD():
    def factorization_(a):
        rep = [[]for _ in range(2)]
        pair = []
        for i in range(2,int(10**(10*1/3))+2):
            cur = 0
            while a%i==0:
                cur += 1
                a //= i
            if cur>0:
                cur %= 3
                if cur==0:
                    continue
                rep[0].append((i,cur))
                pair.append((i,3-cur))
        if not rep[0]:
            rep[0].append((0,0))
        rep[1] = a
        rep[0] = tuple(rep[0])

        rep = tuple(rep)
        pair = tuple(pair)
        return rep, pair

    def square(a):
        rep = set()
        for i in range(1,a+1):
            rep.add(i**2)
        return rep

    N = I()
    S = [I()for _ in range(N)]
    group = defaultdict(int)
    P = defaultdict(tuple)
    for s in S:
        g,p = factorization_(s)
        group[g] += 1
        P[g[0]] = p
    #print(group)
    G2 = deepcopy(group)
    #print(P)
    sq = square(int(10**(5))+1)
    used = set()
    ans = 0
    for key,c in group.items():
        rep, rest = key
        if (rep,rest) in used:
            continue
        if rest in sq:
            pair = int(pow((rest+1),0.5))
        else:
            pair = rest**2
        if rep==((0,0),) and rest==1:
            ans += 1
        else:
            ans += max(c,G2[(P[rep],pair)])
            used.add((P[rep], pair))
        #print(ans)
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Wrong Answer

Solution code:
def examA():
    S = SI()
    if "W" in S and not "E" in S:
        print("No")
    elif "E" in S and not "W" in S:
        print("No")
    elif "N" in S and not "S" in S:
        print("No")
    elif "S" in S and not "N" in S:
        print("No")
    else:
        print("Yes")
    return

def examB():
    N = I()
    A = [I()for _ in range(N)]
    ans = 0
    for i in range(N-1):
        ans += A[i]//2
        if A[i]%2 and A[i+1]>=1:
            ans += 1
            A[i+1] -= 1
    ans += A[N-1]//2
    print(ans)
    return

def examC():
    N = I()
    A = [I()for _ in range(N)]
    if N==1:
        print(0)
        return
    odd = set()
    for i in range(N):
        if i&1==0:
            odd.add(A[i])
    A.sort()
    ans = 0
    for i in range((N+1)//2):
        if A[i*2] in odd:
            continue
        ans += 1
    print(ans)
    return

def examD():
    def factorization_(a):
        rep = [[]for _ in range(2)]
        pair = []
        for i in range(2,int(10**(10*1/3))+2):
            cur = 0
            while a%i==0:
                cur += 1
                a //= i
            if cur>0:
                cur %= 3
                if cur==0:
                    continue
                rep[0].append((i,cur))
                pair.append((i,3-cur))
        if not rep[0]:
            rep[0].append((0,0))
        rep[1] = a
        rep[0] = tuple(rep[0])

        rep = tuple(rep)
        pair = tuple(pair)
        return rep, pair

    def square(a):
        rep = defaultdict(int)
        for i in range(1,a+1):
            rep[i**2] = i
        return rep

    N = I()
    S = [I()for _ in range(N)]
    group = defaultdict(int)
    P = defaultdict(tuple)
    for s in S:
        g,p = factorization_(s)
        group[g] += 1
        P[g[0]] = p
    #print(group)
    G2 = deepcopy(group)
    #print(P)
    sq = square(int(10**(0.5))+1)
    used = set()
    ans = 0
    for key,c in group.items():
        rep, rest = key
        if (rep,rest) in used:
            continue
        if sq[rest]>0:
            pair = sq[rest]
        else:
            pair = rest**2
        if rep==((0,0),) and rest==1:
            ans += 1
        else:
            ans += max(c,G2[(P[rep],pair)])
            used.add((rep,rest))
            used.add((P[rep], pair))
        #print(ans)
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()

"""

"""