사용자 도구

사이트 도구


ps:problems:boj:3142

즐거운 삶을 위한 노력

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

풀이

  • 곱한 수를 계속 유지하면서 계산하는 것은 당연히 불가능하므로, 수를 소인수분해한 형태로 관리하면 된다.
  • 제곱수인지 여부만 확인하면 되므로, 각 소수 인자의 개수가 홀수인지 짝수인지만 구분해서 홀수개인 인자들만 모아서 관리하면 된다.
  • 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()

토론

댓글을 입력하세요:
M X C L N
 
ps/problems/boj/3142.txt · 마지막으로 수정됨: 2024/02/23 03:17 저자 teferi