백준 2824 최대공약수

쉬운 정수론 문제
https://www.acmicpc.net/problem/2824

math.gcd로 간단히 풀었다.

import math
import sys; input = sys.stdin.readline
n = int(input())
n_arr = list(map(int ,input().split()))
m = int(input())
m_arr = list(map(int, input().split()))

N = 1
for i in range(n):			# 곱한 값 
    N *= n_arr[i]

M = 1
for i in range(m):
    M *= m_arr[i]
ans = gcd(N, M)
print(str(ans)[-9:]) 		# 아홉 자리만 출력!

다만, 이러면 정수론 연습이 안되서 유클리드 호제법을 두 가지 형태로 구현하는 법을 연습 했다.

# 기본형
def gcd(a,b):
    while b > 0:
    	tmp = b%a
        a, b = b, tmp
   	return a
        
# 재귀
def gcd(a, b):
	if b == 0:
    	return a
    gcd(b, a%b)

다만, 재귀로 구현한 gcd를 이용해 이 문제를 풀려고 할 경우 RecursionError가 날 것이다.
재귀를 쓸 때는 항상 최대 깊이를 고려해야 한다.