[BOJ, 백준] 2824 최대공약수 Python

 

 

 

from collections import defaultdict
import math
N = int(input())
A = list(map(int,input().split()))
M = int(input())
B = list(map(int,input().split()))

div1, div2 = defaultdict(int), defaultdict(int)
#A를 위한것
def a(n):
    t = int(math.sqrt(n)) + 1
    for i in range (2,t):
        if n % i == 0:
            while n % i == 0:
                div1[i] += 1
                n //= i
    if n != 1:
        div1[n] += 1
    return

def b(n):
    t = int(math.sqrt(n)) + 1
    for i in range(2, t):
        if n % i == 0:
            while n % i == 0:
                div2[i] += 1
                n //= i
    if n != 1:
        div2[n] += 1
    return

for aa in A:
    a(aa)
for bb in B:
    b(bb)


num = list(div1.keys())
ans = 1

check = False
for x in num:
    if x in div2:
        ans *= (x ** min(div1[x], div2[x]))
        if ans >= 1_000_000_000:
            check = True
            ans %= 1_000_000_000
if check == True:
    y = len(str(ans))
    ans = "0" * (9-y) + str(ans)
    print(ans)
else:
    print(ans)

곱해져서 A와 B가 된다는 것은 본질적인 질문은 아니라고 생각되는 문제였다. 

 

(괜히 말이 더 어렵게 느껴지는 여지가 있을듯?)

 

A와 B라는 리스트가 주어져 있을 때, 각 요소들을 소인수분해 한 뒤에 최대공약수를 구하는 방침으로 구하면 되겠다.

 

결국 아이디어는 어렵지는 않은 문제인 것 같다.

 

A = x_1^{y_1} * x_2^{y_2} * ... * x_n^{y_n},  B = x_1^{z_1} * x_2^{z_2}* ... * x_n^{z_n}  (Each x_i is prime number)

이런 꼴로 주어져 있을때, A와 B의 최대공약수는

 

gcd(A,B) = x_1^{min(y_1, z_1)} * x_2^{min(y_2, z_2)} * ... * x_n^{min(y_n,z_n)} 이런 꼴로 나타내어진다는 것에 유의 !

사실, 공통인 소인수를 갖지 않는 경우에도 동일한 논리를 적용할 수 있다. ㅎㅎ.