[백준][KOTLIN] 1629 곱셉

- https://www.acmicpc.net/problem/1629

1629번: 곱셈

풀이

- 지수가 0, 1, 홀수, 짝수 일 경우에 대한 점화식을 구한다.

코드

import java.io.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (A, B, C) = br.readLine().split(" ").map { it.toLong() }
    println("${cal(A, B, C) % C}")
}

// A : 자연수
// B : 지수
// C : 나누는 수
private fun cal(a: Long, b: Long, c: Long): Long {
    return when (b) {
        0L -> 1L
        1L -> a
        else -> {
            // 지수가 짝수일 경우
            if (b % 2 == 0L) {
                val temp = cal(a, b / 2, c) % c
                (temp * temp) % c
            } else {
                val temp = cal(a, b / 2, c) % c
                (((temp * temp) % c) * a) % c
            }
        }
    }

}