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: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict


def eratosthenes_generator():
    yield 2
    n = 3
    h = {}
    while True:
        m = n
        if n in h:
            b = h[n]
            m += 2 * b
            while m in h:
                m += 2 * b
            h[m] = b
            del h[n]
        else:
            m += 2 * n
            while m in h:
                m += 2 * n
            h[m] = n
            yield n
        n += 2


gen = eratosthenes_generator()
p = 0
primes = []
for p in gen:
    if p > 2154:
        break
    primes.append(p)

prime_pairs = {1: 1, p: p * p, p * p: p}
for p in gen:
    if p > 100000:
        break
    p2 = p * p
    prime_pairs[p] = p2
    prime_pairs[p2] = p

n, *sss = map(int, sys.stdin.buffer.read().split())
normalized = defaultdict(int)
over_pairs = {}
frac_pairs = {}
ans = 0
for s in sss:
    # sを2154までの素数で全て割る → ～10^5 までの単一の素数またはその2乗以外は、10^10 までの範囲にペアは存在し得ない
    frac = 1  # 2154までの素因数について、立方数とならない端数を掛け合わせたもの
    pair = 1  # 2154までの素因数について、立方数となるためにペアに求められる因数
    for p in primes:
        if s < p:
            break
        x = 0
        d, m = divmod(s, p)
        while m == 0:
            x += 1
            s = d
            d, m = divmod(s, p)
        x %= 3
        if x == 1:
            frac *= p
            pair *= p ** 2
        elif x == 2:
            frac *= p ** 2
            pair *= p
    if s > 2154 and s not in prime_pairs:
        ans += 1
        continue
    frac_pairs[frac] = pair
    normalized[s, frac] += 1

if (1, 1) in normalized:
    ans += 1
    del normalized[1, 1]

tmp = 0
for (s, frac), cnt in normalized.items():
    pair = (prime_pairs[s], frac_pairs[frac])
    if pair not in normalized:
        tmp += cnt * 2
    else:
        tmp += max(cnt, normalized[pair])
ans += tmp // 2

print(ans)

Submission status: Time Limit Exceeded

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**(3.4))+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**(3.3)),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: Time Limit Exceeded

Solution code:
"""
Rを立法数とする
a * R と a**2 * R a**1 * R → a**2*R a**1*R a**2*R
3つはなれてるとあかん！！　でも取り除かれてるはずだよな…
→Rを取り除いて後はDP

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


Rを取り除く→10**3.333333以下の素数の3乗で割れるか確かめる

対になるsの導出：
素因数分解→10**5まで試し割(割れて10**5以下になったらdivlis方式に変える)
→巨大素数ばっかりだと死ぬ
2乗して新たに生まれたRを取り除けばok！！！！
→範囲は？10**6.6666以下か？(やばくね？)

sと対になるsでは片方しか取れない(dicで管理するかぁ)
sと対sの中で小さい方に合わせてdicで管理かなぁ
"""
def Sieve(n): #n以下の素数全列挙(O(nloglogn)) retは素数が入ってる。divlisはその数字の素因数が一つ入ってる

    ret = []
    divlis = [-1] * (n+1) #何で割ったかのリスト(初期値は-1)
    
    flag = [True] * (n+1)
    flag[0] = False
    flag[1] = False

    ind = 2
    while ind <= n:

        if flag[ind]:
            ret.append(ind)

            ind2 = ind ** 2

            while ind2 <= n:
                flag[ind2] = False
                divlis[ind2] = ind
                ind2 += ind

        ind += 1

    return ret,divlis


N = int(input())
dic = {}

ret,divlis = Sieve(4641589)
div3 = 0

for loop in range(N):

    s = int(input())
    ndic = {}

    for i in ret:

        while s % i == 0:
            if i not in ndic:
                ndic[i] = 1
            else:
                ndic[i] += 1
            s //= i

        if s < len(divlis) or i ** 2 > s:
            break

    #print (s,"now",loop)

    while s < len(divlis) and divlis[s] != -1:
        if divlis[s] not in ndic:
            ndic[divlis[s]] = 1
        else:
            ndic[divlis[s]] += 1

        s //= divlis[s]

    if s != 1:
        if s not in ndic:
            ndic[s] = 1
        else:
            ndic[s] += 1

    S = 1
    T = 1
    #print (ndic)
    for i in ndic:
        S *= i ** (ndic[i] % 3)
        T *= i ** ((-1 * ndic[i]) % 3)

    #print (S,T)

    if S == T:
        div3 += 1
    elif S < T:
        if S not in dic:
            dic[S] = [1,0]
        else:
            dic[S][0] += 1
    else:
        if T not in dic:
            dic[T] = [0,1]
        else:
            dic[T][1] += 1

ans = min(1,div3)

for i in dic:
    ans += max(dic[i])

print (ans)

Submission status: Time Limit Exceeded

Solution code:
"""
Rを立法数とする
a * R と a**2 * R a**1 * R → a**2*R a**1*R a**2*R
3つはなれてるとあかん！！　でも取り除かれてるはずだよな…
→Rを取り除いて後はDP

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


Rを取り除く→10**3.333333以下の素数の3乗で割れるか確かめる

対になるsの導出：
素因数分解→10**5まで試し割(割れて10**5以下になったらdivlis方式に変える)
→巨大素数ばっかりだと死ぬ
2乗して新たに生まれたRを取り除けばok！！！！
→範囲は？10**6.6666以下か？(やばくね？)

sと対になるsでは片方しか取れない(dicで管理するかぁ)
sと対sの中で小さい方に合わせてdicで管理かなぁ
"""
def Sieve(n): #n以下の素数全列挙(O(nloglogn)) retは素数が入ってる。divlisはその数字の素因数が一つ入ってる

    ret = []
    divlis = [-1] * (n+1) #何で割ったかのリスト(初期値は-1)
    
    flag = [True] * (n+1)
    flag[0] = False
    flag[1] = False

    ind = 2
    while ind <= n:

        if flag[ind]:
            ret.append(ind)

            ind2 = ind ** 2

            while ind2 <= n:
                flag[ind2] = False
                divlis[ind2] = ind
                ind2 += ind

        ind += 1

    return ret,divlis


N = int(input())
dic = {}

ret,divlis = Sieve(4641589)
div3 = 0

for loop in range(N):

    s = int(input())
    ndic = {}

    for i in ret:

        while s % i == 0:
            if i not in ndic:
                ndic[i] = 1
            else:
                ndic[i] += 1
            s //= i

        if s < len(divlis):
            break

    #print (s,"now",loop)

    while s < len(divlis) and divlis[s] != -1:
        if divlis[s] not in ndic:
            ndic[divlis[s]] = 1
        else:
            ndic[divlis[s]] += 1

        s //= divlis[s]

    if s != 1:
        if s not in ndic:
            ndic[s] = 1
        else:
            ndic[s] += 1

    S = 1
    T = 1
    #print (ndic)
    for i in ndic:
        S *= i ** (ndic[i] % 3)
        T *= i ** ((-1 * ndic[i]) % 3)

    #print (S,T)

    if S == T:
        div3 += 1
    elif S < T:
        if S not in dic:
            dic[S] = [1,0]
        else:
            dic[S][0] += 1
    else:
        if T not in dic:
            dic[T] = [0,1]
        else:
            dic[T][1] += 1

ans = min(1,div3)

for i in dic:
    ans += max(dic[i])

print (ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def input_ints():
    return list(map(int, input().split()))

def output_list(v):
    print(' '.join(str(x) for x in v))

n = 10 ** 5
a = [True] * n
primes = []
for x in range(2, n):
    if not a[x]:
        continue
    primes.append(x)
    for y in range(2 * x, n, x):
        a[y] = False

def degen(x):
    for p in primes:
        while x % (p ** 3) == 0:
            x //= p ** 3
    return x

def main():
    n = int(input())
    ans = 0
    d = defaultdict(int)
    for i in range(n):
        x = degen(int(input()))
        if x == 1:
            ans = min(ans + 1, 1)
        else:
            d[x] += 1
    used = set()
    for x, c in d.items():
        if x in used:
            continue
        y = degen(x * x)
        if y in d:
            ans += max(c, d[y])
            used.add(y)
        else:
            ans += c
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
cls = { i*i*i for i in range(10**7)}

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: Time Limit Exceeded

Solution code:
import collections

def f(x):
    p = 2
    t1 = t2 = 1
    while p**2 <= x:
        while x % p**3 == 0:
            x //= p**3
        if x % p**2 == 0:
            t2 *= p
            x //= p**2
        if x % p == 0:
            t1 *= p
            x //= p
        p += 1
    return (t1 * x, t2)

c = collections.Counter(f(int(input())) for _ in range(int(input())))
print((sum(c[t1, t2] for t1, t2 in c if (c[t1, t2], t1) > (c[t2, t1], t2)) + min(1, c[1, 1])))

Submission status: Time Limit Exceeded

Solution code:
import collections

def f(x):
    f = list()
    p = 2
    while p**2 <= x:
        while x % p == 0:
            f.append(p)
            x //= p
        p += 1
    if x > 1:
        f.append(x)
    c = collections.Counter(f)
    return tuple(tuple(x for x in c if c[x] % 3 == k) for k in (1, 2))

c = collections.Counter(f(int(input())) for _ in range(int(input())))
print((sum(c[t1, t2] for t1, t2 in c if (c[t1, t2], t1) > (c[t2, t1], t2)) + min(1, c[(), ()])))

Submission status: Time Limit Exceeded

Solution code:
MAX_N=int(1e5);
MAX_SQRT=int(2e3);

N=0;

pflg=[True for i in range(MAX_SQRT+1)];
prime=[];

def sieve():
  pflg[0]=pflg[1]=False;
  for i in range(2,MAX_SQRT+1):
    if pflg[i]:
      prime.append(i);
      for j in range(i*i,MAX_SQRT+1,i):
        pflg[j]=False;

mp={};

N=int(input());
sieve();
for i in range(N):
  s=int(input());
  for p in prime:
    c=p*p*p;
    while (s%c)==0:
      s/=c;
  mp[s]=mp.get(s,0)+1;
ans=0;
for i in mp:
  if (i==1):
    continue;
  pa=i*i;
  for p in prime:
    c=p*p*p;
    while (pa%c)==0:
      pa/=c;
  a=mp[i];
  mp[i]=0;
  if pa in mp:
    a=max(a,mp[pa]);
    mp[pa]=0;
  ans+=a;
if mp[1]>0:
  ans+=1;
print(ans);

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict

def soe(num):
    input_list = [False if i%2==0 or i%3==0 or i%5==0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5]=True
    sqrt = math.sqrt(num)

    for serial in range(3,num,2):
        if serial >= sqrt:
            return input_list
        for s in range(serial**2, num, serial):
            input_list[s] = False

primes=[]
bool_list = soe(int((10**10)**(1/3)))
for i in range(0,len(bool_list)):
    if bool_list[i]:
        primes.append(i)

n=int(input())
srr=[]
for i in range(0,n):
    srr.append(int(input()))

dic=defaultdict(int)
for s in srr:
    tmp=defaultdict(int)
    for p in primes:
        while s%p==0:
            s//=p
            tmp[p]+=1
            tmp[p]%=3
    if s!=1:
        tmp[s]=1
#    print(tmp)
    tmp_norm=[]
#    for k in sorted(tmp.keys()):
    for k in tmp.keys():
        if tmp[k]!=0:
            tmp_norm.append((k,tmp[k]))
#    print(tuple(tmp_norm))
    dic[tuple(tmp_norm)]+=1
#print(dic)

norm_list = list(dic.keys())
pair_list = []

#print(norm_list)
for t in norm_list:
    tmp=[]
    for elem in t:
        tmp.append((elem[0],3-elem[1]))
    pair_list.append(tuple(tmp))
#print(pair_list)

total=0
for i in range(0,len(norm_list)):
    if norm_list[i]==():
        total+=2
    elif dic[pair_list[i]]==0:
        total+=dic[norm_list[i]]*2
    else:
        total+=max(dic[norm_list[i]],dic[pair_list[i]])
print(total//2)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict

def soe(num):
    input_list = [False if i%2==0 or i%3==0 or i%5==0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5]=True
    sqrt = math.sqrt(num)

    for serial in range(3,num,2):
        if serial >= sqrt:
            return input_list
        for s in range(serial**2, num, serial):
            input_list[s] = False

primes=[]
bool_list = soe(int((10**10)**(1/3)))
for i in range(0,len(bool_list)):
    if bool_list[i]:
        primes.append(i)

n=int(input())
srr=[]
for i in range(0,n):
    srr.append(int(input()))

dic=defaultdict(int)
for s in srr:
    tmp=defaultdict(int)
    for p in primes:
        while s%p==0:
            s//=p
            tmp[p]+=1
            tmp[p]%=3
    if s!=1:
        tmp[s]=1
#    print(tmp)
    tmp_norm=[]
    for k in sorted(tmp.keys()):
        if tmp[k]!=0:
            tmp_norm.append((k,tmp[k]))
#    print(tuple(tmp_norm))
    dic[tuple(tmp_norm)]+=1
#print(dic)

norm_list = list(dic.keys())
pair_list = []

#print(norm_list)
for t in norm_list:
    tmp=[]
    for elem in t:
        tmp.append((elem[0],3-elem[1]))
    pair_list.append(tuple(tmp))
#print(pair_list)

total=0
for i in range(0,len(norm_list)):
    if norm_list[i]==():
        total+=2
    elif dic[pair_list[i]]==0:
        total+=dic[norm_list[i]]*2
    else:
        total+=max(dic[norm_list[i]],dic[pair_list[i]])
print(total//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
count = {}
revd = {}
get = count.get
for e, c in Counter(int(raw_input()) for i in xrange(input())).items():
    res = rev = 1
    j = 2
    while j*j <= e:
        if e % j == 0:
            cnt = 0
            while e % j == 0:
                e /= j
                cnt += 1
            if cnt%3:
                res *= j**(cnt%3)
                rev *= j**(3-(cnt%3))
        j += 1
    res *= e
    rev *= e**2
    count[res] = get(res, 0) + c
    if res <= rev:
        revd[res] = rev
    else:
        revd[rev] = res
if 1 in count:
    one = 1 - count[1]
else:
    one = 0
print one + sum(max(get(u, 0), get(v, 0)) for u, v in revd.items())

Submission status: Time Limit Exceeded

Solution code:
count = {}
revd = {}
get = count.get
for i in xrange(input()):
    e = int(raw_input())
    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)
            if cnt%3:
                rev *= j**(3-(cnt%3))
        j += 1
    res *= e
    rev *= e**2
    count[res] = get(res, 0) + 1
    revd[res] = rev
ans = 0
if 1 in count:
    ans = 1 - count[1]
for u, cu in count.items():
    v = revd[u]
    cv = get(v, 0)
    if cv:
        if u <= v:
            ans += max(cu, cv)
    else:
        ans += cu
print ans

Submission status: Accepted

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[:-1]:
        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: Accepted

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
        if int(n**0.5)**2 == n:
            res2 *= int(n**0.5)
        else:
            res1 *= n
        return res1 * res2 * res2, res1 * res1 * res2

    N, *S = map(int, sys.stdin.buffer.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: Accepted

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 * int(tmp_s ** 0.5)
    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: Accepted

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())
    news=1
    invs=1
    for p in prime:
        a=ind(p,s)
        s//=p**a
        news*=p**(a%3)
        invs*=p**((-a)%3)
    if s==1 or int(s**0.5)**2!=s:
        news*=s
        invs*=s**2
        if news not in dic:
            dic[news]=0
            inverse[news]=0
        dic[news]+=1
        inverse[news]=invs
    else:
        news*=s
        invs*=int(s**0.5)
        if news not in dic:
            dic[news]=0
            inverse[news]=0
        dic[news]+=1
        inverse[news]=invs

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

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)
    i //= i
  if i != 1:
    continue
  if x in dc:
    ans -= min(dc[x],v)
    dc[x] = 0
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def prime_sieve(start, 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]:
            if i >= start:  
                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(1,315)
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)])
mid_primes = prime_sieve(315,5500)
rev_mid_primes = dict()
for i in mid_primes:
  for j in mid_primes:
    if i == j:
      continue
    rev_mid_primes[i**2*j] = j**2*i
    
    
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])
  elif rem in rev_mid_primes:
    another.append(rev_mid_primes[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: Accepted

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**(3.4))+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**(3.3)),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)
    ans = 0
    for key,c in group.items():
        rep, rest = key
        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 (P[rep],pair) in group:
                if c < group[(P[rep], pair)]:
                    ans += group[(P[rep], pair)]
                else:
                    ans += c
                group[(P[rep], pair)] = 0
            else:
                ans += c
            group[key] = 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: Accepted

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

def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1<<32 else [2, 3, 5, 7, 11, 13, 17] if n < 1<<48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8 + 1
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r-k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x-ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n//g): return n//g
def primeFactor(N):
    i = 2
    ret = {}
    n = N
    mrFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i%2
        if i == 101 and n >= 2**20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    mrFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if mrFlg > 0: ret = {x: ret[x] for x in sorted(ret)}
    return ret

N = int(input())
ans = 0
D = {}
for _ in range(N):
    pf = primeFactor(int(input()))
    a, b = 1, 1
    for p in pf:
        a *= p ** (pf[p] % 3)
        b *= p ** (-pf[p] % 3)
    if a not in D: D[a] = 0
    if a == b:
        if D[a] == 0: ans += 1
    else:
        if b not in D: D[b] = 0
        if D[b] <= D[a]: ans += 1
    D[a] += 1

print(ans)