백준 1850 : 최대공약수

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

1850번: 최대공약수

 

문제

---

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

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

---

입력

---

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

---

출력

---

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

---

풀이

n자리의 1로만 이루어진 수를 N, m자리의 1로만 이루어진 수를 M이라고 하자. (n >= m)

우리가 구해야하는 것은 N과 M의 최대 공약수, GCD(N, M)이다.

 

유클리드 호제법을 무작정 적용하면 n, m의 크기 제한이 2^63보다 작은 자연수이기 때문에, N, M을 너무 큰 수가 되어 담을 자료형이 존재하지 않을 것이다.

 

N과 M이 모든 자릿수가 1로만 이루어진 수라는 성질을 이용하자.

n - m 이 0보다 크거나 같은 정수이므로, N은 10^(n-m) * M + 10^(n-m-1) + ... + 1 꼴의 형태로 표현할 수 있다.

 

N을 M의 배수를 자릿수 단위로 묶어서 GCD 연산 과정에서 고려하지 않을 수 있다.

=> 0≤ n-km < m 을  만족하는 자연수 k는 항상 존재한다. (n ≥ m), n부터 n-km 까지는 k개의 묶음으로 N의 일부를

M의 배수로 처리할 수 있다. 그러면 우리가 고려해야할 자리수는? 10^(n%m) 부터만 다시 고려하면 된다.

 

위의 연산에서 종료조건은 언제일까?

n이 m으로 완전히 나누어지는 순간,  즉, n%m=0인 순간의 m이 최대 공약수의 자리수가 될 것이다.