[백준 2824번] 파이썬 - 최대공약수

백준 2824 - 최대공약수

시간 제한 1초, 메모리 제한 192MB

# 조건

• 상근이는 학생들에게 두 양의 정수 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을 출력해야 한다)

# 접근 방법

• 파이썬의 경우 숫자의 범위를 신경쓰지 않아도 되서 쉽게 풀리는 문제였다.
• math 라이브러리의 gcd 함수를 사용하여 최대공약수를 구해준 후, 9자리가 넘어가면 뒤에서부터 9번째부터 출력해주면 된다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
from math import gcd

a, b = 1, 1
flag = False
for _ in range(2):
    N = int(input())
    nums = list(map(int, input().split()))
    for i in nums:
        a *= i
    if not flag:
        b = a
        a = 1
    flag = True
c = str(gcd(a, b))
if len(c) >= 9:
    print(c[-9:])
else:
    print(c)