[백준] 1629 곱셈

 

🔒 문제

 

 

🧠 아이디어

$$ A^B % C $$

 

1. 시간 복잡도

A를 그대로 B 번 곱하면 O(AB) 시간이 걸리고 A 와 B가 모두 Int 최대일때 2^64에 가까운 시간복잡도를 갖게된다.

 

어떻게 하면
시간 복잡도를 낮출 수 있을까?

$$ O (Log B) $$

로 해결할 수 있게되었다.

 

이 때, 주의해야 할 것이 지수승이 '짝수'냐 '홀수'냐에 따라 분기되어야 한다는 것이다.

예를 들면

A^6 % c == (A^3 % c * A^3 %c) %c

지만

A^7 % c == (A^3 % c * A^3 %c A^1 % c) %c 로 나뉘어야한다.

 

/2 연산을 할 때 피제수가 홀수인 경우 나머지 1이 버려지기 때문이다.

 

2. 자료형

 

Int 자료형은 4바이트로 

$$ ~ 2^{32} - 1 $$

Long 자료형이 8바이트로 

$$ ~ 2^{64} - 1 $$ 의 수의 범위를 갖는다는 것을 기억해야한다.

 

3. Modular 성질

 

여기서의 핵심은 모듈로 연산에 대한 성질을 미리 알고있어야 한다.

이 내용에 대해서는 아래 링크를 참조하면 되겠다.

Modular 연산

 

 

 

 

🔑 Kotlin Code

import java.io.BufferedReader
import java.io.InputStreamReader

// 모듈러 성질 : (a * b) % c = (a % c * b % c) % c
private fun getAB(A: Long, B: Long, C: Long) : Long {
	// Base Condition
    if (B == 1L) return A % C
    val nextNum = getAB(A, B / 2, C)
    // 지수가 짝수일 때 
    return if (B % 2 == 0L) nextNum * nextNum % C
    // 결합 법칙을 이용하여 수가 3개가 아닌 2개까지만 곱해지도록
    // ⚠️ 3개의 숫자를 곱하면 over flow 가능성이 생김
    // ex) 2^32 * 2^32 * 또 다른 수 => overflow
    // 지수가 홀 수 일 때는 A % C 를 또 걸어줘야함.
    else ((nextNum * nextNum % C) * (A % C)) % C
}

// B == 짝수 일 때 A 하위 곱
// A % C 는 이미 base condition 에서 이미 불러와짐.
// A^2 % c == (A % c) * (A % c) % c
// A ^ 3 % c == ((A % c) * (A % c) * A^1 % c) %C
// A ^ 7 % c == ((A^3 % c) * (A^3 %c) * A % C) % C
// 결합법칙을 적용시 (nextNum * nextNum * A) % C
// (nextNum * nextNum % C * A % C) % C

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (A, B, C) = br.readLine().split(" ").map(String::toLong)
    print(getAB(A, B, C))
}