[Kotlin] 백준 1629 : 곱셈

문제 링크

1629번: 곱셈

---

---

문제 해설

\(A^B\mod C\)를 구해야 한다. 그런데 \(A\), \(B\), \(C\) 모두 최대치가 Int.MAX_VALUE이기 때문에 정말 정직하게 거듭제곱을 하면 무조건 시간초과가 발생한다. 따라서 효율적인 방법을 찾아서 해결해야 한다.

 

이 문제는 지수 법칙을 이용하면 수월하게 해결할 수 있다. \(x^{2n}=(x^2)^n\)인 성질과 \(x{n+m}=x^n\times x^m\)인 성질을 이용하여 지수를 계속 반으로 나누면서 밑을 제곱하는 것이다. 예를 들어 \(2^{14}\)를 지수 법칙을 이용해서 구한다고 생각해보자. \(2^{10}=(2^2)^7\)이 된다. 여기서 \(2^2\)을 계산하여 \(2^{10}=4^7\)이 된다.(\(2\times 1\)번 계산)

여기서 새로운 지수인 7는 홀수이기 때문에 별도의 계산을 할 필요가 있다. 반으로 나누고 남는 지수가 1이므로 현재의 밑인 4는 별도로 곱해야할 수 \(x\)에 저장해놓는다. 그 후 남은 지수인 4를 반으로 나누어 밑을 제곱하면 \(2^{14}=(4^2)^3\times x\)가 된다. 여기서도 \(4^2\)을 계산하여 \(2^{14}=16^3\times x\)가 된다.(\(2\times 2+1\)번 계산)

새로운 지수인 3 또한 홀수이기 때문에 별도로 곱해야할 \(x\)에 현재의 밑인 16을 곱한다. 그리고 남은 지수인 2를 반으로 나누면 1이기 때문에 그냥 그대로 계산을 하면 \(2^{14}=16^2\times x=2^{14}=256\times x\)가 된다. (\(2\times 3+2\)번 계산)

일련의 계산을 진행하는 동안 \(x=4\times 16=64\)가 되었다. 따라서 \(2^{14}=256\times 64=16,384\)가 된다. (\(2\times 3+3\)번 계산)

 

위의 과정을 거치는 것으로 단순히 거듭제곱하면 14번 계산을 해야했던 것을 \(2\log{14}+3\)번의 계산으로 끝내게 되었다. 시간복잡도로 나타내면 \(O(n)\)이 \(O(\log{n})\)으로 혁신적으로 줄어든 것이다.

 

문제에서는 \(A^B\)를 \(C\)로 나눈 나머지를 구하라고 했으므로, 위에서 진행한 거듭제곱을 구하는 과정에서 \((a\times b) \mod c=(a\mod c)\times (b\mod c)\)인 점을 이용하여 \(C\)로 나누는 연산만 적절하게 추가해주면 된다.

---

Code

fun main() = with(System.`in`.bufferedReader()) {
    var (a, b, c) = readLine().split(' ').map { it.toLong() }
    var result = 1L
    while (b > 0) {
        if (b % 2 == 1L) result = (result * a) % c
        a = (a * a) % c
        b /= 2
    }
    print(result)
}