[JAVA] 백준 (실버1) 1629번 곱셈

링크

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

---

문제 설명

정답률 27.178%

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

---

입력 예제

10 11 12

---

출력 예제

4

---

풀이

단순히 A를 B번 곱하여 C로 나누면 시간 초과가 발생한다. 최댓값이 $2^32 - 1$ 이므로 3번만 곱해도 long의 범위를 벗어난다.

그래서 다음과 같이 분할한다.
$a^4 = a^2 \times a^2 = (a \times a) \times (a \times a)$
$a^5 = a^2 \times a^2 \times a = (a \times a) \times (a \times a) \times a$

코드로 구현하면 다음과 같다.

static long pow(long base, long exp) {

    //지수가 1일 때
    if (exp == 1) {
        return base;
    }
    
    //지수를 1/2하여 재귀 호출
    long half = pow(base, exp / 2);
    //호출한 결과를 두번 곱함
    long result = half * half;
    
    //지수가 홀수일 때
    if (exp % 2 == 1) {
        return result * base;
    }
    
    return result;
}

이제 C로 나누어야 되는데 위 함수의 반환값에 모듈러 연산을 적용한다.

static long pow(long base, long exp, long divisor) {

    if (exp == 1) {
        return base % divisor;
    }
    
    long half = pow(base, exp / 2, divisor);
    long result = half * half;
    
    if (exp % 2 == 1) {
        return (result % divisor) * (base % divisor);
    }
    
    return result % divisor;
}

코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        long pow = pow(A, B, C);
        System.out.println(pow);
    }

    static long pow(long base, long exp, long divisor) {

        //지수가 1일 때
        if (exp == 1) {
            return base % divisor;
        }

        //지수를 1/2하여 재귀 호출
        long half = pow(base, exp / 2, divisor);
        //호출한 결과를 두번 곱함
        long result = half * half;

        //지수가 홀수일 때
        if (exp % 2 == 1) {
            return (result % divisor) * (base % divisor);
        }

        return result % divisor;
    }
}