백준 2824 최대공약수

풀이 과정

• 각 인수마다 최대공약수를 찾아서 답에 계속 곱해주는 방식을 생각함.
  • 2, 4 처럼 공통된 인수는 중복으로 반영됨
    -> 구한 값으로 해당 인수를 나눠줘야 함.

import sys
input = sys.stdin.readline
A = int(input())
A_lst = list(map(int, input().split()))
B = int(input())
B_lst = list(map(int, input().split()))

def divide(x, y):
    r = x % y
    while r != 0:
        x = y
        y = r
        r = x % y
    return y
ans = 1
for i in range(A):
    for j in range(B):
        div = divide(A_lst[i], B_lst[j])
        ans *= div
        A_lst[i] = A_lst[i] // div
        B_lst[j] = B_lst[j] // div
print(A_lst, B_lst)
if ans >= 100000000:
    ans = str(ans)
    ans = ans[len(ans)-9:]
print(ans)

• divide 함수는 최대공약수를 구하는 함수.
  • x와 y의 최대공약수는 y와 x%y (x를 y로 나눈 나머지)의 최대공약수와 같음을 이용
• 모든 인수에 대해 최대공약수를 구하고, ans에 계속해서 곱해나간다.
  • 중복을 없애기 위해 해당 인수를 최대공약수로 나눠줘야한다.
  • 그렇지 않으면 다음 루프에서 다시 참조할 수 있음.
  • 해당 반례

    3
    2 3 4
    2
    2 4