[백준][코틀린] 1629 곱셈

문제 내용

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제 입력	예제 출력
10 11 12	4

문제 풀이

본 문제는, Kotlin의 BigInteger을 사용해도 풀리기는 한다. 하지만, 문제의 의도가 그걸 원한건 아닐테고.. 그렇게 푼다고 해서 실력이 는다 생각하지도 않아서, 문제의 의도대로 분할 정복을 이용해서 풀었다. 

지수가 짝수일 땐, \(2^{10}\) = \(2^5\) * \(2^5\) 로 나뉠 것이고,
지수가 홀수일 땐, \(2^{11}\) = \(2^5\) * \(2^5\) * 2 로 나뉠 것이다. 

그럼 여기서 나머지를 구하려고 % c 만 해주면 될까? 그렇지 않다.

answer의 최댓값이 \(2^{31}-1\) 일때, answer * answer 까지는 \(2^64\)라 Long 범위 안이지만, 여기에 a를 곱해버리면 범위를 넘어 오버플로우가 발생한다. 그러면 어떻게 해야될까? 

이때, 모듈러의 합동공식을 사용하게 된다.

https://st-lab.tistory.com/237

난 위 링크를 참고했고, 공식을 익혔다!! 이에 따라 분리해서 계산을 하면 Long의 범위를 넘지 않고 계산할 수 있다. 

</>̆̈ 코드

fun main() {
    val (a, b, c) = readLine()!!.split(" ").map { it.toLong() }
    print(division(a, b, c))
}

private fun division(a: Long, b: Long, c: Long): Long {
    return when {
        b == 1L -> a % c
        b % 2 == 0L -> {
            val answer = division(a, b/2, c)
            (answer * answer) % c
        }
        else -> {
            val answer =  division(a, b/2, c)
            ((answer * answer % c) * a) % c
        }
    }
}

링크

1629번: 곱셈