[백준] 1850번: 최대공약수 - Kotlin[코틀린]

문제

 

1850번: 최대공약수

 

---

풀이

 

 입력받은 두 자연수의 최대 공약수가 모든 자리가 1로만 이루어져있는 두 자연수의 최대 공약수의 자리수가 된다. 따라서 입력받은 수의 최대 공약수를 구하고 최대 공약수만큼 1을 출력해주면 된다.

 

 예제 입력 2를 보면 3 과 6의 최대 공약수는 3이고 답은 111이다. 11111 = 111 x 1001로 나타낼수 있기 때문에 답은 맞다. 풀이가 왜 성립하는지의 증명은 https://www.acmicpc.net/board/view/32699 에서 jh05013님의 답변을 참고하였다. 다음은 그 증명이다.

 

주제

두 수의 최대공약수가 1로 표현한 수의 최대공약수의 자리수와 같다는 명제의 수학적 귀납법 증명

 

기본 단계
a = b인 경우, gcd(a, b) = a이고, 따라서 gcd((1이 a개), (1이 b개)) = (1이 a개)이다. 따라서, a + b = 2인 경우에도 명제는 성립한다.

귀납 단계
a + b = 2, 3, ..., k까지 명제가 성립한다고 가정한다. a + b = k + 1인 경우, 다음과 같이 증명할 수 있다.

gcd((1이 a개), (1이 b개)) = gcd((1이 a-b개, 0이 b개), (1이 b개))

(1이 a개) - (1이 b개)는 (1이 a-b개)와 (0이 b개)로 이루어진 수이다. 따라서, gcd((1이 a개) - (1이 b개), (1이 b개)) = gcd((1이 a-b개), (1이 b개))이다.

증명
1. gcd(x, y) = gcd(x-y, y) 성질을 적용하면, 다음과 같이 된다.

gcd((1이 a개), (1이 b개)) = gcd((1이 a-b개, 0이 b개), (1이 b개))

2. 10의 거듭제곱은 (1이 b개)와 서로소이다. 따라서, 다음과 같이 된다.

gcd((1이 a-b개, 0이 b개), (1이 b개)) = gcd((1이 a-b개), (1이 b개))

3. 귀납적 가정에 의해, (1이 a-b개)의 1의 개수는 gcd(a-b, b)와 같습니다. 따라서, 다음과 같이 된다.

gcd((1이 a-b개), (1이 b개)) = (1이 gcd(a-b, b)개)

4. gcd(x, y) = gcd(x-y, y) 성질을 다시 적용하면, 다음과 같이 된다.

(1이 gcd(a-b, b)개) = (1이 gcd(a, b)개)

따라서, a + b = k + 1인 경우에도 명제는 성립한다.

 

---

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    with(br.readLine().split(' ').map { it.toLong() }) {
        bw.write("1".repeat(gcd(this[0], this[1]).toInt()))
    }
    bw.flush()
    bw.close()
    br.close()
}

fun gcd(num1: Long, num2: Long): Long {
    var a = num1
    var b = num2

    while (b > 0L) {
        val tmp = a
        a = b
        b = tmp%b
    }

    return a
}