백준 2824번 : 최대공약수 [Python]

https://www.acmicpc.net/problem/2824

2824번: 최대공약수

 

 

문제 

상근이는 학생들에게 두 양의 정수 A와 B의 최대공약수를 계산하는 문제를 내주었다. 그런데, 상근이는 학생들을 골탕먹이기 위해 매우 큰 A와 B를 주었다.

상근이는 N개의 수와 M개의 수를 주었고, N개의 수를 모두 곱하면 A, M개의 수를 모두 곱하면 B가 된다.

이 수가 주어졌을 때, 최대공약수를 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다.

셋째 줄에 M(1 ≤ M ≤ 1000)이 주어진다. 넷째 줄에는 M개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, M개의 수를 곱하면 B가 된다.

 

 

 

출력

두 수의 최대공약수를 출력한다. 만약, 9자리보다 길다면, 마지막 9자리만 출력한다. (최대 공약수가 1000012028인 경우에는 000012028을 출력해야 한다)

 

 

예시

 

코드

import sys
import math

A = int(sys.stdin.readline())
A_list = list(map(int, sys.stdin.readline().split()))
B = int(sys.stdin.readline())
B_list = list(map(int, sys.stdin.readline().split()))

A_num = 1
B_num = 1
for i in A_list:
    A_num *= i
for i in B_list:
    B_num *= i

print(str(math.gcd(A_num, B_num))[-9:])

 

 

코드 해석

• 각 리스트와 수를 받는다
• 각 리스트를 곱하다.
• math 의 gcd 함수를 사용하여 최대공약수를 생성하고 [-9:]를 활용하여 특정 자리만 출력할 수 있게 설정한다.