[BOJ-1850]최대공약수

이전에는 유클리드 호제법을 사용하지 않고, 최대공약수를 구해서 풀었는데

이 문제는 소인수분해를 해서 값을 계산하려니 

최대 1e+19 개 까지 소인수분해를 해야하니 답이 없어서.. 유클리드 호제법를 써보려한다. 

내용은 위키피디아 에서 참고하여 학습하였음.

https://ko.wikipedia.org/wiki/유클리드_호제법

2개의 자연수가 최대공약수를 구하는 알고리즘 중 하나이며,

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘임.

2개의 자연수 A, B에 대해서  (전제조건 A > B의 경우) A를 B로 나눈 나머지를 R 이라 하면,  

A와 B의 최대공약수는 B와 R의 최대 공약수와 같음.

이것을 따라 과정을 반복하면 

B 를 R로 나누어 나머지 R1을 구하고 다시 

R 을 R1 으로 나누어 나머지.. R2를 구하고.. (반복)

해서 나머지가 0이 되었을 때 나누는 수가 A와 B의 최대공약수란 의미이다. 

예제)

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

<과정 1> 

1071 > 1029 

A = B*i + R

1071 = 1029 * 1 + 42

이때 B는 1029, R은 42

B = R*i + R1

1029 = 42*24 + 21

R = R1*i + R2

42 = 21*2 + 0

이므로 가장 마지막에 나온 Rn(나머지) 가 if(R==0)이 되면 이때 Rn-1이 최대공약수가 된다는 의미이다.

------------------------------------------------------------------------------------------------------

이 1850 문제의 예제로 

A = 111 

B = 1111 인 경우 

B > A 이므로 

B = A*i + R1

1111 = 111*10 + 1

A = R1*i + R2

111 = 1*111 + 0 

이므로 R2가 0 이 되므로 R1인 1이 최대공약수가 된다. (A와 B의 최대공약수 1)

------------------------------------------------------------------------------------------------------

A 111 

B 111111 인 경우

B > A 이므로 

B = A*i + R1

111111 = 111*1001 + 0

이때 R1 이 0 이므로 A가 A와 B의 최대 공약수가 된다. (A와 B의 최대공약수 111)

------------------------------------------------------------------------------------------------------

사실 2달전에 C++11로 작성했는데 틀렸다. 

지금에서 다시 풀어보는데... 

문제를 잘못 이해했던 부분도 있었다.

잘못 1 ) 입력의 개수, 1e+19 자리라는 의미 1이 1e+19 개만큼 ...

잘못 2 ) 정답은 천만 ''자리''를 넘지않는다.

잘못 3 ) 입력으로 4인 경우 1111, 5인경우 11111..... 

1e+19개 인경우 ......... 저걸..... 111111111111111111.........11111111111111111111...............ㅁㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

어차피 111........1.....1.1111 인수는 결국엔 최대공약수가 11111....11 로 구성되어 있기 때문에 입력으로.........

들어오는 수의 최대공약수 만큼 1을 출력하면되는 문제였다.......

def gcd(A, B):
    while(True):
        R = A%B
        if(R==0):
            return B
        else:
            A, B = B, R
    
L = map(int, raw_input().split())
 
t=(gcd(max(L), min(L))%10000000)
ans = ''
for i in range(t):
    ans = ans + '1'
print ans