[Python]백준 #2824 최대공약수(큰수자료구조)

사실 이 문제는 복잡하게 문제를 풀어야 하지만,

큰수(big integer)가 지원된다면, 유클리드 알고리즘으로 간단하게 구할 수 있습니다.

보통은 제가 C/C++을 이용해서 풀이를 해오고 있지만, 큰수 자료구조를 사용하기 위해서 파이썬을 이용해보았습니다.

 

GCD

 

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

 

만약 큰수 자료구조를 지원하지 않는다면, 가장 큰 수의 제곱근을 기준으로 해서 그 이하의 소수들에 대하여 공약수를 구하는 방식을 사용해야 합니다.  큰수 자료구조끼리의 연산이 시간이 오래 걸리지만, 이 문제에 있어서는 큰수 자료구조를 사용한다고 해서 문제가 될만큼은 아닙니다.

 

"""
    baekjoon #2824
        - by Aubrey Choi
        - created at 2019-08-19
"""
def gcd(a, b):
    while b!=0:
        t = b
        b = a%b
        a = t
    return a
input()
x = input().split()
a=1
for k in x: a *= int(k)
input()
x = input().split()
b=1
for k in x: b *= int(k)
print(str(gcd(a,b))[-9:])

 

이 코드는 두 집합의 수들의 곱에서 최대공약수를 구하고, 그 결과의 마지막 9자리를 출력하는 문제를 해결하는 파이썬 코드입니다. 이 코드는 `gcd` 함수를 사용하여 두 숫자의 최대공약수(GCD)를 계산합니다.

먼저, 코드는 `gcd`라는 함수로 시작합니다. 이 함수는 두 숫자 `a`와 `b`를 입력받아, `b`가 0이 될 때까지 반복적으로 나머지를 구하면서 최대공약수를 계산합니다. 여기서 `b`가 0이 되면, 남아있는 `a` 값이 최대공약수가 됩니다.

그 후, 코드의 본체가 시작됩니다. 첫 번째로 `input()`을 호출하여 사용자로부터 입력을 받고, 이 입력은 무시됩니다(여기서는 아마도 첫 번째 집합의 크기일 것입니다). 그리고 두 번째 줄에서 실제로 집합의 숫자들을 입력받아 `x` 리스트에 저장합니다. `x` 리스트의 각 요소는 문자열 형태의 숫자이며, 이들은 `int()`를 통해 정수로 변환된 후, 곱셈을 통해 하나의 큰 정수 `a`에 모두 곱해집니다.

이와 동일하게, 두 번째 집합의 숫자들도 같은 방식으로 입력받아 모두 곱한 값이 `b`에 저장됩니다.

마지막으로, `gcd(a, b)`를 호출하여 두 집합의 곱에 대한 최대공약수를 계산하고, 그 결과의 마지막 9자리를 출력합니다. `str(gcd(a,b))[-9:]`는 최대공약수의 값을 문자열로 변환한 후, 뒤에서 9자리의 문자열을 추출하는 역할을 합니다.

이 코드는 입력되는 수의 범위가 매우 클 수 있기 때문에, 계산된 결과값이 아주 큰 숫자가 될 수 있습니다. 이를 고려하여, 출력 시에는 마지막 9자리만 표시하도록 구현한 것입니다.