[백준] 1629번: 곱셈 - Kotlin[코틀린]

문제

 

1629번: 곱셈

 

---

풀이

 

 문제는 A를 B번 곱한 수를 C로 나눈 나머지를 구하는 것이다. 반복문으로 해결하면 시간초과가 발생한다. 풀기 위해서는 지수 법칙과 모듈러 연산 성질에 대해 알고 있어야 한다.

 

 - 지수 법칙: $a^{(n+m)} = a^n \times a^m$

 - 모듈러 연산 곱셈 성질: $(a\times b)\mod c = (a\mod c \times b\mod c)\mod c$

 

 이 두 성질을 활용하여 재귀 함수를 만들면 된다. 함수는 지수가 1이 될 때까지 B를 절반으로 나누어가며 계산한다.

 

 - 지수가 짝수인 경우

    $a^n = a^{n/2} \times a^{n/2}$

    $a^n\mod c = a^{n/2}\mod c \times a^{n/2}\mod c$

 

 - 지수가 홀수인 경우

    $a^n = a^{n/2} \times a^{n/2}\times a$

    $a^n\mod c = a^{n/2}\mod c \times a^{n/2}\mod c\times a\mod c$

 

 반복문을 사용하여 A를 N번 곱하는 경우에는 시간복잡도가 O(N)이지만 분할 정복을 활용하면 O(log N)으로 절약된다.

 

---

코드

 

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

    val(a, b, c) = br.readLine().split(' ').map { it.toLong() }

    bw.write("${powerMod(a, b, c)}")
    bw.flush()
    bw.close()
    br.close()
}

fun powerMod(base: Long, exponent: Long, mod: Long): Long {
    return when(exponent) {
        0L -> 1
        1L -> base % mod
        else -> {
            val n = powerMod(base, exponent / 2, mod)

            if(exponent % 2 == 0L) (n * n) % mod
            else ((n * n) % mod) * base % mod
        }
    }
}