1850 최대공약수

1로 이뤄진 두 수의 최대공약수를 구하는 문제다. 1로 이뤄진 수의 성질을 이용하면 쉽게 찾을 수 있다.

1로 이뤄진 수를 나눌 수 있는 수는 똑같이 1로 이뤄진 수이다

111 111111의 두 수가 있다. 1이 3개, 1이 6개다. 1이 3개인 111의 큰 수로 모든 수를 나눌 수 있다

111 11111111의 두 수가 있다. 오른쪽 1의 개수는 8개로 증가했다. 1이 1개인 수가 최대공약수가 된다.

규칙을 찾아보면 1의 개수로 이뤄진 개수들의 최대공약수를 구하면 된다

첫 예에선 3, 6의 최대공약수인 3이 답이었고

다음 예에선 3, 8의 최대공약수인 1이 답이었다

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

https://github.com/surinoel/boj/blob/master/1850.c