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:
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

    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)
    used = set()
    ans = 0
    for key,c in group.items():
        rep, rest = key
        if (rep,rest) in used:
            continue
        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()

"""

"""

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

    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)
    ans = 0
    for key,c in group.items():
        rep, rest = key
        pair = rest**2
        if rep==((0,0),) and rest==1:
            ans += 1
        else:
            ans += max(c,G2[(P[rep],pair)])
            G2[(rep,rest)] = 0
            if G2[(P[rep], pair)]:
                group[(P[rep], pair)] = 0
        #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

    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)
    ans = 0
    for key,c in group.items():
        rep, rest = key
        pair = rest**2
        if rep==((0,0),) and rest==0:
            ans += 1
        else:
            ans += max(c,G2[(P[rep],pair)])
            G2[(rep,rest)] = 0
            if G2[(P[rep], pair)]:
                group[(P[rep], pair)] = 0
        #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))+1):
            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
    N = I()
    S = [I()for _ in range(N)]
    group = defaultdict(int)
    P = defaultdict(tuple)
    for i in range(N):
        g,p = factorization_(S[i])
        group[g] += 1
        P[g[0]] = p
    #print(group)
    G2 = deepcopy(group)
    #print(P)
    ans = 0
    for key,c in group.items():
        rep, rest = key
        pair = rest**2
        if rep==((0,0),):
            ans += min(c,1)
        else:
            ans += max(c,G2[(P[rep],pair)])
            G2[(rep,rest)] = 0
            if G2[(P[rep], pair)]:
                group[(P[rep], pair)] = 0
        #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:
import sys
readline = sys.stdin.readline
from collections import Counter
LIMIT = 2200
M = LIMIT**2
prime = [0]*M
for i in range(2, M):
    if prime[i]:
        continue
    for j in range(i, M, i):
        if not prime[j]:
            prime[j] = i

def pd(x):
    C = Counter()
    while x > 1:
        C[prime[x]] += 1
        x //= prime[x]
    return C

def prsh(N):
    prime = [2]
    for L in range(3,N):
        for p in prime:
            if not L % p:
                break
            if p > L**(1/2):
                prime.append(L)
                break
    return prime

PRIME = prsh(LIMIT)
SP = set(p for p in range(1, M) if prime[p] == p)
SP2 = Counter({p**2: p for p in SP})
MAXS = 10**10
N = int(readline())

L = []

match = Counter()
table = Counter()
for i in range(N):
    s = int(readline())
    ctr = 1
    res = 1
    for p in PRIME:
        if s < p:
            break
        cnt = 0
        while s%p == 0:
            s //= p
            cnt += 1
        if cnt % 3:
            res *= p**(3 - cnt%3)
            ctr *= p**(cnt%3)
        if res > MAXS:
            res = 0    
    else:
        ctr *= s
        if s in SP:
            res *= s**2
        elif SP2[s]:
            res *= SP2[s]
        else:
            res = 0
    match[ctr] = res
    table[ctr] += 1

ans = 0
seen = set()
for k, v in table.copy().items():
    if k == 1:
        ans += min(v, 1)
        continue
    if k in seen:
        continue
    ans += max(v, table[match[k]])
    seen.add(match[k])
    seen.add(k)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
from collections import Counter
LIMIT = 2200
M = LIMIT**2
prime = [0]*M
for i in range(2, M):
    if prime[i]:
        continue
    for j in range(i, M, i):
        if not prime[j]:
            prime[j] = i

def pd(x):
    C = Counter()
    while x > 1:
        C[prime[x]] += 1
        x //= prime[x]
    return C

def prsh(N):
    prime = [2]
    for L in range(3,N):
        for p in prime:
            if not L % p:
                break
            if p > L**(1/2):
                prime.append(L)
                break
    return prime

PRIME = prsh(LIMIT)
SP = set(PRIME)
SP2 = Counter({p**2: p for p in PRIME})
MAXS = 10**10
N = int(readline())

L = []

match = Counter()
table = Counter()
for i in range(N):
    s = int(readline())
    ctr = 1
    res = 1
    for p in PRIME:
        if s < p:
            break
        cnt = 0
        while s%p == 0:
            s //= p
            cnt += 1
        if cnt % 3:
            res *= p**(3 - cnt%3)
            ctr *= p**(cnt%3)
        if res > MAXS:
            res = 0    
    else:
        ctr *= s
        if s in SP:
            res *= s**2
        elif SP2[s]:
            res *= SP2[s]
        else:
            res = 0
    match[ctr] = res
    table[ctr] += 1

ans = 0
seen = set()
for k, v in table.copy().items():
    if k == 1:
        ans += min(v, 1)
        continue
    if k in seen:
        continue
    ans += max(v, table[match[k]])
    seen.add(match[k])
    seen.add(k)
print(ans)

Submission status: Wrong Answer

Solution code:
"""
Rを立法数とする
a * R と a**2 * R は片方だけ取れる
→Rを取り除いて後はDP

どうやって立法数を取り除く？
10**3.3まで試し割り？→5secだから間に合うかなぁ
"""

N = int(input())

mul3s = []
i = 2
while i**3 <= 10**10:
    mul3s.append(i**3)
    i += 1

div3 = []

dic = {}
div2 = []

for i in range(N):

    s = int(input())

    for j in mul3s:
        while s % j == 0:
            s //= j
        if s < j:
            break

    if s == 1:
        div3.append(s)
    elif s not in dic:
        dic[s] = 1
        div2.append(s)
    else:
        dic[s] += 1

div2.sort()

pdic = {}
dpdic = {}

for i in div2:

    if (int(i**0.5) ** 2 == i and int(i**0.5) not in dic) or int(i**0.5)**2 != i:
        dpdic[i] = [dic[i]]
        pdic[i] = i
    else:
        dpdic[pdic[int(i**0.5)]] .append (dic[i])
        pdic[i] = pdic[int(i**0.5)]

#print (dpdic)

ans = min(1,len(div3))

for nlis in dpdic:

    dp = [0] * 2 #0=前の奴を使ってない 1=使った

    for i in dpdic[nlis]:
        ndp = [0] * 2
        ndp[0] = max(dp[0] , dp[1])
        ndp[1] = dp[0] + i
        dp = ndp

    ans += max(dp)

print (ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
from collections import Counter

N = int(input())

S = np.array(sys.stdin.readlines(), dtype=np.int64)

U = int(10 ** 3.4)
is_prime = np.zeros(U+1, dtype=np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(3,U+1,2):
    if p*p > U:
        break
    if is_prime[p]:
        is_prime[p*p::2*p] = 0

primes = is_prime.nonzero()[0]

# 3乗で割る
for p in primes:
    tr = p*p*p
    while True:
        bl = (S % tr == 0)
        if bl.any():
            S[bl] //= tr
        else:
            break

square_part = np.ones_like(S)
free_part = S.copy() # 厳密には違うが
for p in primes:
    sq = p*p
    bl = (S % sq) == 0
    free_part[bl] //= sq
    square_part[bl] *= p
# 相手が自分より小さいならば必ず正しく計算できている
opposite = free_part * free_part * square_part

x_to_y = dict(zip(S,opposite))

counter = Counter(S)
answer = 0
for x,cx in counter.items():
    if x == 1:
        answer += 1
        continue
    y = x_to_y[x]
    if x < y:
        # とりあえずxを採用しておく
        answer += cx
        continue
    cy = counter[y]
    answer -= cy
    answer += max(cx,cy)

print(answer)

Submission status: Wrong Answer

Solution code:
cls = { i*i*i for i in range(10**6)}
 
n = int(raw_input())
ls = [int(raw_input()) for _ in range(n)]
ls.sort()
l = []
for i in ls:
    for j in l:
        if i*j in cls:
            break
    else:
        l.append(i)
print len(l)

Submission status: Wrong Answer

Solution code:
n = input()
S = [int(raw_input()) for i in xrange(n)]

count = {}
revd = {}
for i in xrange(n):
    e = S[i]
    res = rev = 1
    j = 2
    while j*j <= e:
        if e % j == 0:
            cnt = 0
            while e % j == 0:
                e /= j
                cnt += 1
            res *= j**(cnt%3)
            rev *= j**(3-(cnt%3))
        j += 1
    res *= e
    rev *= e**2
    count[res] = count.get(res, 0) + 1
    revd[res] = rev
ans = 0
used = set()
for u in revd:
    if u in used:
        continue
    if u == 1:
        ans += 1
        continue
    cu = count[u]
    v = revd[u]
    cv = count.get(v, 0)
    used.add(u)
    if cv:
        ans += max(cu, cv)
        used.add(v)
    else:
        ans += cu
print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

def eratosthenes_sieve(n):
    table = [0] * (n + 1)
    prime_list = []
    
    for i in xrange(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in xrange(i + i, n + 1, i):
                table[j] = 1
    
    return prime_list

def trial_division_sqrt(n):
    prime_count = collections.Counter()
    
    for i in xrange(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[n] += 1
    
    for p, c in prime_count.iteritems():
        prime_count[p] = c % 3
    
    return prime_count

def trial_division_prime(n, prime_list):
    prime_count = collections.Counter()
    
    for i in prime_list:
        if i * i > n:
            break
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[n] += 1
    
    for p, c in prime_count.iteritems():
        prime_count[p] = c % 3
    
    return prime_count

table = eratosthenes_sieve(int(10**5.1))

N = n()

primes = {}
freq = collections.Counter()
S = []
for i in xrange(N):
    s = n()
    primes[s] = trial_division_prime(s, table)
    v = 1
    for p, c in primes[s].iteritems():
        if c == 0:
            continue
        v *= p ** c
    if v < s:
        primes[v] = primes[s]
        s = v
    freq[s] += 1
    S.append(s)

S.sort()

c = 0
banned = set()
for s in S:
    if s in banned:
        continue
    if s == 1:
        c += 1
        banned.add(1) 
        continue
    candidate = 1
    for p, p_count in primes[s].iteritems():
        if p_count == 0:
            continue
        candidate *= p**(3 - p_count)
    if s < candidate:
        if freq[s] >= freq[candidate]:
            c += freq[s]
        else:
            c += freq[candidate]
        banned.add(s)
        banned.add(candidate)

print c

Submission status: Wrong Answer

Solution code:
import math
import collections

p_max = int(10**(10./3))

marked = [True]*2+[False]*(p_max-2)
ps = []

for n in range(2,p_max):
    if marked[n]:
        continue
    ps.append(n)
    for n2 in range(n, p_max):
        if n2 % n == 0:
            marked[n2] = True

def getexp(n, p):
    ans = 0
    while n > 1 and n % p == 0:
        ans += 1
        n = n // p
    return ans

def getcanon(n):
    canon = []
    for p in ps:
        if n == 1:
            return tuple(canon)
        e = getexp(n, p)
        n = n//(p**e)
        if e % 3 != 0:
            canon.append((p, e % 3))
    sqr = int(math.sqrt(n+0.5))
    if sqr**2 == n:
        canon.append((sqr, 2))
    else:
        canon.append((n,1))
    return tuple(canon)

def getcomp(canon):
    return tuple([(p,3-e) for (p,e) in canon])


N = int(raw_input())
s = [int(raw_input()) for i in range(N)]

ctr = collections.Counter()

for si in s:
    ctr[getcanon(si)] += 1

ans = 0

cans = list(ctr.keys())

for can in cans:
    ct = ctr[can]
    if ct == 0:
        continue
    if can == ():
        ans += 1
        ctr[can] = 0
        continue
    comp = getcomp(can)
    c_ct = ctr[comp]
    if c_ct == 0:
        ans += ct
    else:
        ans += max(ct, c_ct)
        ctr[comp] = 0



print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

def eratosthenes_sieve(n):
    table = [0] * (n + 1)
    prime_list = []
    
    for i in xrange(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in xrange(i + i, n + 1, i):
                table[j] = 1
    
    return prime_list

def trial_division_sqrt(n):
    prime_count = collections.Counter()
    
    for i in xrange(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[n] += 1
    
    for p, c in prime_count.iteritems():
        prime_count[p] = c % 3
    
    return prime_count


N = n()

primes = {}
freq = collections.Counter()
S = []
for i in xrange(N):
    s = n()
    primes[s] = trial_division_sqrt(s)
    v = 1
    for p, c in primes[s].iteritems():
        if c == 0:
            continue
        v *= p ** c
    if v < s:
        s = v
        primes[s] = trial_division_sqrt(s)
    freq[s] += 1
    S.append(s)

S.sort()

c = 0
banned = set()
for s in S:
    if s in banned:
        continue
    if s == 1:
        c += 1
        banned.add(1) 
        continue
    candidate = 1
    for p, p_count in primes[s].iteritems():
        if p_count == 0:
            continue
        candidate *= p**(3 - p_count)
    if s < candidate:
        if freq[s] >= freq[candidate]:
            c += freq[s]
        else:
            c += freq[candidate]
        banned.add(s)
        banned.add(candidate)

print c

Submission status: Time Limit Exceeded

Solution code:
q=[1]*100003
p=[]
q[0]=0
q[1]=0
for i in range(2,100001):
  if q[i]:
    p.append(i)
    for j in range(i*2,100001,i):
      q[j]=0

def f(x):
  r=[]
  for i in range(len(p)):
    i=p[i]
    if x%i==0:
      r.append(i)
      r.append(0)
      while x%i==0:
        r[-1]+=1
        x//=i
      r[-1]%=3
      if r[-1]==0:
        del r[-1]
        del r[-1]
  if x!=1:
    r.append(x)
    r.append(1)
  return r

def g(x):
  r=[]
  for i in range(len(x)):
    r.append(x[i])
    if i&1:
      r[i]=3-r[i]
  return r

N=int(input())
S=[f(int(input())) for i in range(N)]
D=dict()
for i in range(N):
  D[tuple(S[i])]=D.get(tuple(S[i]),0)+1
P=0
E=dict()
X=0
Y=list(D.keys())
for i in range(len(Y)):
  if len(Y[i])==0:
    P+=1
    continue
  X=tuple(g(Y[i]))
  if E.get(Y[i],0):
    continue
  E[X]=1
  P+=max(D[Y[i]],D.get(X,0))
print(P)

Submission status: Time Limit Exceeded

Solution code:
p=[]
for i in range(2,100000):
  for j in range(len(p)):
    if i%p[j]==0:
      i=0
      break
  if i:
    p.append(i)

def f(x):
  r=[]
  for i in range(len(p)):
    i=p[i]
    if x%i==0:
      r.append(i)
      r.append(0)
      while x%i==0:
        r[-1]+=1
        x//=i
      r[-1]%=3
      if r[-1]==0:
        del r[-1]
        del r[-1]
  if x!=1:
    r.append(x)
    r.append(1)
  return r

def g(x):
  r=[]
  for i in range(len(x)):
    r.append(x[i])
    if i&1:
      r[i]=3-r[i]
  return r

N=int(input())
S=[f(int(input())) for i in range(N)]
D=dict()
for i in range(N):
  D[tuple(S[i])]=D.get(tuple(S[i]),0)+1
P=0
E=dict()
X=0
Y=list(D.keys())
for i in range(len(Y)):
  if len(Y[i])==0:
    P+=1
    continue
  X=tuple(g(Y[i]))
  if E.get(Y[i],0):
    continue
  E[X]=1
  P+=max(D[Y[i]],D.get(X,0))
print(P)

Submission status: Time Limit Exceeded

Solution code:
def f(x):
  r=[]
  for i in range(2,int(x**0.5)+1):
    if x%i==0:
      r.append(i)
      r.append(0)
      while x%i==0:
        r[-1]+=1
        x//=i
      r[-1]%=3
      if r[-1]==0:
        del r[-1]
        del r[-1]
  if x!=1:
    r.append(x)
    r.append(1)
  return r

def g(x):
  r=[]
  for i in range(len(x)):
    r.append(x[i])
    if i&1:
      r[i]=3-r[i]
  return r

N=int(input())
S=[f(int(input())) for i in range(N)]
D=dict()
for i in range(N):
  D[tuple(S[i])]=D.get(tuple(S[i]),0)+1
P=0
E=dict()
X=0
Y=list(D.keys())
for i in range(len(Y)):
  if len(Y[i])==0:
    P+=1
    continue
  X=tuple(g(Y[i]))
  if E.get(Y[i],0):
    continue
  E[X]=1
  P+=max(D[Y[i]],D.get(X,0))
print(P)

Submission status: Time Limit Exceeded

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

def main():
    N, *S = sys.stdin.read().split()
    T = []
    inv_dict = {}
    for s in S:
        factors = list(map(int, Popen(["factor", s], stdout=PIPE).communicate()[0].split()[1:]))
        t = 1
        t_inv = 1
        for f, group in groupby(factors):
            n = len(list(group)) % 3
            if n == 1:
                t *= f
                t_inv *= f * f
            elif n == 2:
                t *= f * f
                t_inv *= f
        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: Time Limit Exceeded

Solution code:
def get_anti_key(n: int):
    prime_factors = []
    for k in range(2, int(n ** 0.5) + 1):
        cnt = 0
        while n % k == 0:
            cnt += 1
            n = n // k
        if cnt != 0:
            prime_factors.append((k, cnt))
    if n != 1:
        prime_factors.append((n, 1))
    anti_key = 1
    for key, cnt in prime_factors:
        anti_key *= key ** ((3 - cnt) % 3)
    return anti_key


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


# 立方数のリスト
pow3 = [i ** 3 for i in range(2, 50)]

# s[i] が立方数で割り切れるときは割る
for i in range(n):
    for div in pow3:
        while s[i] % div == 0:
            s[i] //= div

# 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 = get_anti_key(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: Time Limit Exceeded

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 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)