[백준] 1850번 최대공약수 - 유클리드 호제법(Python)

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

1850번: 최대공약수

최대공약수를 구하는 간단한 문제이다.

주의할 점은 주어지는 입력값의 최대 공약수를 구하는 것이 아닌 입력값 만큼의 1로 구성된 숫자의 최대 공약수를 구해야 한다는 것이다.

 

사용 알고리즘

최대 공약수를 구할 때 사용되는 알고리즘은 유클리드 호제법이다.

유클리드 호제법
두 양의 정수 a,b에 대하여 a = bq + r (q는 몫, r은 나머지이며 0<= r <b)이라 할 때, a, b의 최대 공약수는 b, r의 최대 공약수와 같다. 이때 r = 0이라면, a,b의 최대공약수는 b가 된다.

 

풀이

주어진 A, B를 1로 이루어진 숫자로 변환한 뒤 유클리드 호제법을 사용한다면 간단하게 풀리겠지만, 주어진 범위는 2^63보다 작은 자연수이므로 입력한 값을 변한 한 뒤 처리하는 것은 시간 초과가 날 것이다. 이러한 문제점 앞에서 고민을 하다가 식을 나열해보게 되었다.

 

입력된 값이 8 5라고 가정해본다면 우리는 11,111,111과 11,111사이의 최대 공약수, 즉 gcd(11111111, 11111)를 구해야 하는 것이다.

11,111 = 10^4 + 10^3 + 10^2 + 10^1 + 10^0 이고

11,111,111 = 10^7 + 10^6 + 10^5 + 10^4 + 10^3 + 10^2 + 10^1 + 10^0

                  = 10^3 ( 10^4 + 10^3 + 10^2 + 10^1 + 10^0) + 10^2 + 10^1 + 10^0

                  = 11,111 * 10^3 +111  로 표현할 수 있다. 

 

다시말해 굳이 입력값을 1로 이루어진 숫자로 변환 할 필요없이 입력값 A, B 그대로 유클리드 호제법을 적용해도 문제가 풀린다는 것이다.

 

gcd(11111111, 11111) = gcd(11111, 111)

-> gcd(8, 5) = gcd(5, 3) 

예제1 ) 입력값 3, 4의 최대 공약수는 1이다 -> 1

예제2 ) 입력값 3, 6의 최대 공약수는 3이다 -> 111

예제3 ) 입력값 500000000000000000, 500000000000000002의 최대 공약수는 2이다 -> 11

Python

n, m = map(int,input().split())

if n>m:

    n,m = m,n

def gcd(a,b):

    if (a%b==0):

        return b

    else:

        return gcd(b, a%b)

   

k = gcd(m,n)

for i in range(k):

    print(1,end='')