ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 3142 |
문제명 | 즐거운 삶을 위한 노력 |
레벨 | 골드 2 |
분류 |
소인수분해 |
시간복잡도 | O(a + nlogloga) |
인풋사이즈 | a<=1,000,000, n<=500,000 |
사용한 언어 | Python 3.11 |
제출기록 | 97924KB / 900ms |
최고기록 | 900ms |
해결날짜 | 2024/02/23 |
"""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()