• 곱한 수를 계속 유지하면서 계산하는 것은 당연히 불가능하므로, 수를 소인수분해한 형태로 관리하면 된다.
• 제곱수인지 여부만 확인하면 되므로, 각 소수 인자의 개수가 홀수인지 짝수인지만 구분해서 홀수개인 인자들만 모아서 관리하면 된다.
• n개의 입력에 대해서 소인수분해를 해야 하는데, 이때는 최소인수를 전처리하는 방식으로 처리하면, O(a)의 전처리 이후에, 각각의 쿼리를 O({x의 소인수 개수})에 처리할수 있다.
• 총 시간 복잡도는 O(a + nlogloga)

"""Solution code for "BOJ 3142. 즐거운 삶을 위한 노력".

- Problem link: https://www.acmicpc.net/problem/3142
- Solution link: http://www.teferi.net/ps/problems/boj/3142

Tags: [number theory]
"""

import sys
from teflib import numtheory


def main():
    N = int(sys.stdin.readline())
    a = [int(sys.stdin.readline()) for _ in range(N)]

    odd_count_factors = set()
    calc = numtheory.PrimeFactorizationCalculator(max(a) + 1)
    for a_i in a:
        for p, count in calc.prime_factorization(a_i).items():
            if count % 2 == 1:
                if p in odd_count_factors:
                    odd_count_factors.remove(p)
                else:
                    odd_count_factors.add(p)
        print('NE' if odd_count_factors else 'DA')


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.PrimeFactorizationCalculator