[1850] 최대공약수 (유클리드 호제법)

1850번: 최대공약수

 

유클리드 호제법

두 수의 최대 공약수를 구하는 알고리즘

1. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
2. 앞 단계에서 작은 수와 MOD 연산 결과값(나머지)으로 MOD 연산을 수행한다.
3. 단계 2를 반복하다가 나머지가 0이되는 순간의 작은 수를 최대 공약수로 선택한다.

 

풀이

"""
모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.
예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.
첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 263보다 작은 자연수이다.
"""
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

a, b = map(int, input().split())
result = gcd(a, b)
while result > 0:
    print(1, end='')
    result -= 1

import math
print('1' * math.gcd(*map(int, input().split())))