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

링크

1629번: 곱셈

풀이

aⁿ을 그대로 계산하면 O(n) 시간이 걸리기 때문에,
분할 정복을 이용한 거듭제곱으로 O(log n)에 해결합니다.

• n이 홀수라면 → $a^n = a \cdot a^{n-1}$
• n이 짝수라면 → $a^n = (a^{n/2})^2$

모듈러 연산을 통해 오버플로우(overflow)를 방지하고,
메모이제이션(Memoization)으로 중복 계산을 방지합니다.

코드

val powerCache = HashMap<Long, Long>()
fun power(a: Long, b: Long, c: Long): Long {
    if (powerCache[b] != null) return powerCache.getValue(b)

    return when {
        b == 0L -> 1L
        b % 2 != 0L -> a * power(a, b - 1, c) % c
        else -> power(a, b / 2, c) * power(a, b / 2, c) % c
    }.also { powerCache[b] = it }
}

fun main() {
    val (a, b, c) = readln().split(" ").map { it.toLong() }

    println(power(a, b, c))
}