#353 백준 파이썬 [1850] 최대공약수

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

 

SOLUTION

무엇인가 규칙은 있어보인다.

유클리드 호제법으로 때려박으면 메모리 초과가 난다. (입력되는 수는 최대 2^63이다!)

하지만 어떤 과정을 거쳐서 되는지 모르겠다면,

유클리드 호제법으로 11111111~ 과 111111111~이 어떤 연관성을 가지는지 알아보자. 우리는 프로그래머다

def gcd(x,y):
    mod = x % y
    while mod >0:
        x = y
        y = mod
        mod = x % y
    return y
    
for A in range(1, 30):
    for B in range(1, 30):
        C = int('1' * A)
        D = int('1' * B)
        print(A, B, len(str(gcd(C, D))))

이런식으로 구성해보면 A, B와 출력되는 111111111~ 의 길이를 알 수 있다.

출력은 다음과 같이 나온다.

1과 11111~의 최대공약수는 당연히 1이다.

11과 1111111~은 이상하게도 격으로 1,2를 반복한다.

111은 3번째마다 배수를 가진다. 111,111 그리고 111,111,111 순으로.

이제 감이 오는가?

1,111,111,111은 정확히, 2, 4, 5, 6, 8 10 번째 것들과 2이상의 배수를 지닌다.

즉 다시  말해, 두 수의 1의 개수(A,B)끼리의 배수만 구하면 되는 것이다.

굳이 1111~수로 바꿀 필요가 없다.

정답인 최대공약수만 1111~형태로 변환해주면 된다.

PYTHON CODE

#유클리드 호제법으로 공약수를 구해줌
def gcd(x,y):
    mod = x % y
    while mod >0:
        x = y
        y = mod
        mod = x % y
    return y    

A, B = map(int, input().split())
print('1' * gcd(A, B))