[BOJ/백준] 곱셈 (S1)

문제

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

풀이

그냥 단순하게 풀면 BufferOverflow 및 시간 초과가 발생하므로 분할 정복을 활용해야 하며, 지수 법칙과 모듈러 방식을 사용하여 진행해야 한다.

 

지수 법칙은 a^(n+m) = a^n * a^m으로 이를 활용하여 지수가 짝수인 경우와 홀수인 경우의 전개를 보면 아래와 같다.

이를 트리 구조로 표현해 보면 아래와 같이 되는 것을 확인할 수 있다.

여기까지만 간단하게 코드를 작성해보면 아래와 같다.

public static long pow(long A, long exponent) {
        // 지수가 1일 경우 A^1 이므로 A % C를 리턴
        if (exponent == 1) return A % C;

        // 지수의 절반에 해당하는 A^(B/2)를 구한다.
        long temp = pow(A, exponent/2);

        // 지수가 홀수인 경우
        if (exponent % 2 == 1) {
            return temp * temp * A;
        }
        // 지수가 짝수인 경우
        return temp * temp;
    }

 

이제는 C를 나눈 나머지 값을 구해야 하는데 지수가 홀수인 경우에 return (temp * temp * A) % C를 하면 BufferOverflow가 발생한다.

따라서 모듈러 산술(Modular Arithmetic)을 이용하여 변형을 해야 한다.

이를 이용하여 (temp * temp * A) % C에 적용을 해보겠다.

(temp * temp * A) % C = ((temp * temp % C) * (A % C)) % C
                      = (((temp * temp % C) % C) * ((A % C) % C))) % C
                      = (temp * temp % C) * (A % C) % C
                      = (temp * temp % C) * A % C

변형을 적용하면 홀수의 경우의 반환값으로 (temp * temp % C) * A % C가 된다. 이를 적용한 최종 코드는 아래의 코드가 된다.

Code

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static long C;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        long A = Integer.parseInt(st.nextToken());
        long B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        long result = pow(A, B);
        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }

    /**
     * 분할 정복을 이용한 거듭제곱 계산 함수로 a^b를 계산하면서 중간에 c로 나눈 나머지를 유지하여 숫자가 너무 커지지 않도록 방지(BufferOverflow)
     */
    public static long pow(long A, long exponent) {
        // 지수가 1일 경우 A^1 이므로 A % C를 리턴
        if (exponent == 1) return A % C;

        // 지수의 절반에 해당하는 A^(B/2)를 구한다.
        long temp = pow(A, exponent/2);

        // 지수가 짝수인 경우와 홀수인 경우로 리턴 값이 달라짐
        if (exponent % 2 == 1) {
            /**
             * 현재 지수가 홀수인 경우?
             * ex) exponent = 홀수 -> A^exponent = A^(exponent/2) * A^(exponent/2) * A
             * 가 되므로 A를 한 번 더 곱해줘야 한다.
             *
             * return temp * temp * A % C로 진행하면 long 형의 범위를 넘김
             * -> 모듈러 공식 사용 => (a * b) % C = (a % C * b % C) % C
             *  (temp * temp * a) % C = ((temp * temp % C) * (a % C)) % C = (((temp * temp % C) % C) * ((A % C) % C))) % C 인데 (x%C)%C = x%C 이므로
             *  = (temp * temp % C) * (a % C) % C = (temp * temp % C) * a % C 가 됨.
             */
            //return temp * temp * A % C;
            return (temp * temp % C) * A % C;
        }
        // 지수가 짝수 인 경우
        return temp * temp % C;
    }
}