1850. 최대공약수

문제

풀이

예제 1일 때 생각해보자
3 => 111
4 => 1111이다.

1111 , 111의 최대공약수는 1이다.

마찬가지로
3 => 111
6 => 111111
111, 111111의 최대공약수는 111이다.

여기서 알 수 있듯이 a, b의 최대공약수를 구하고 최대공약수만큼 1을 써주면 된다.

하지만 입력되는 수는 2^63이므로 상당히 큰 수이다. 이럴 때 유클리드 호제법을 사용하면 된다.

유클리드 호제법

1071과 10929의 최대공약수를 구하면,

1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. => 42
1029는 42로 나누어떨어지지 않기 때문에 1029를 42로 나눈 나머지를 구한다. => 21
42는 21로 나누어떨어진다.
따라서 최대공약수는 21이다.

소스코드

import sys
from collections import deque
sys.stdin = open("input.txt", "r")
input = sys.stdin.readline
for test_case in range(1):
    a, b = map(int, sys.stdin.readline().split())

    max_num = max(a,b)
    min_num = min(a,b)

    while True:
        if max_num % min_num == 0:
            print('1' * min_num)
            break
        rest = max_num% min_num
        max_num = min_num
        min_num = rest