[BOJ, 백준] 13206 Professor KCM Python

 

 

 

결국 이 문제에서 중요한것은, 칠판에 쓰인 숫자들의 "최소공배수"는 얼마인가? 라는 것으로 귀결된다.

 

여기서 중요한 것은,

 

1. 칠판에 쓰인 숫자들이 얼마정도 중복되어 있는가? 그렇다면 중복되어 있지 않은 숫자들은 무엇인가?

2. 최소공배수를 어떻게 구할 것인가? 

 

최소공배수에 대한 아이디어는 공약수의 차수를 비교하는 방식으로 하면 좋을 것 같다.

답안의 코드는 다음과 같다.

import sys
from collections import defaultdict
input = sys.stdin.readline
p = 1_000_000_007
number = [False for _ in range (0,1001)]
prime_number = []
for i in range (2, 1001):
    if number[i] == False:
        prime_number.append(i)
        for j in range (2*i, 1001, i):
            number[j] = True

T = int(input())
for _ in range (0,T):
    numbers = defaultdict(int)
    N = int(input())
    num = list(map(int,input().split()))
    answer = 1
    for x in num:
        numbers[x] = 1
    num_list = list(numbers.keys())
    #num_list가 갯수를 줄인것
    answer = defaultdict(int)
    for x in num_list:
        while x != 1:
            for y in prime_number:
                cnt = 0
                while x % y == 0:
                    x //= y
                    cnt += 1
                answer[y] = max(answer[y], cnt)
    ans = 1
    for x in answer:
        ans *= (x ** answer[x])
        ans %= p
    print(ans % p)