20302. 민트초코

모두 소인수분해 해준 뒤 각 소인수마다의 지수를 변화시킨다고 생각하면 된다.

곱하기를 만나면 지수가 +1이 되고, 나누기를 만나면 지수가 -1이 된다.

유리수가 되려면 지수가 음수인 소인수가 존재하면 된다.

그래서 소인수 분해를 어떻게 하냐면 -> 에라토스테네스의 체 개념을 이용하면 된다.

 

import sys
input = sys.stdin.readline

def primelist() :
    primes = [i for i in range(10**6+1)]
    
    for i in range(2, (10**3)+1) :
        if primes[i] != i :
            continue
        for j in range(i*i, 10**6+1, i) :
            if primes[j] != j :
                continue
            primes[j] = i
    return primes

def calc_exp(exponents, n, flag, primes) :
    while n > 1 :
        exponents[primes[n]] += flag
        n//=primes[n]
    return exponents

def deter_mint(arr) :
    flag = 0
    exponents = [0 for _ in range(10**6+1)]
    primes = primelist()
    for i in range(len(arr)) :
        if i%2 == 0 :
            continue

        num = abs(int(arr[i]))
        if arr[i-1] == '*' :
            flag = 1
            if int(num) == 0 :
                return "mint chocolate"
        
        elif arr[i-1] == '/' :
            flag = -1

        exponents = calc_exp(exponents, num, flag, primes)
    
    for i in exponents :
        if i < 0 : 
            return "toothpaste"
    return "mint chocolate"

n = int(input())
arr = input().rstrip().split()
print(deter_mint(['*'] + arr))

나름 깔끔하게 짜보겠다고 짰는데 실제로 깔끔한지는 잘 모르겠다...