[백준] 최대공약수

1850번: 최대공약수

🔗 문제

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오.

예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

입력

첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 2^63
보다 작은 자연수이다.

$ test1
3 4

$ test2
3 6

$ test3
500000000000000000 500000000000000002

출력

첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다.

$ test1
1

$ test2
111

$ test3
11

💡풀이 방법

최대공약수: 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같고 b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복

• 직접 최소공배수 구하기
  1. b와 a%b의 최대공약수를 구하는데 계속 반복한다.
  2. 결과만큼 1을 출력한다.
• 최대공약수(GCD: Greatest Common Divisor)를 구하는 함수: math.gcd()

💻 코드

# [1850] 최대공약수 - 함수 구현
def GCD(a, b):
    if b == 0:
        return a 
    else:
        return GCD(b, a%b)
while True:
    try:
        a, b = map(int, input().split())
        print(GCD(a, b)*"1")
    except EOFError:
        break

# [1850] 최대공약수 - math.gcd
import math 
while True:
    try:
        a, b = map(int, input().split())
        print(math.gcd(a,b) *"1")
    except EOFError:
        break