[필수 문제] 거듭 제곱 구하기 L

1. 문제

n과 m이 주어질 때, n의 m승을 구하는 프로그램을 작성하시오. 단, n의 m승의 값이 커질 수 있기 때문에, 정답을 10,007 으로 나눈 나머지를 출력한다.

---

입력

첫 번째 줄에 숫자 n과 m이 주어진다. ( 1 ≤ n ≤ 100, 1 ≤ m ≤ 1,000,000,000,000,000,000 ) 

출력

첫째 줄에 n의 m승을 10,007 으로 나눈 나머지를 출력한다.

예제 입력

3 4

예제 출력

81

 

 

 

2. 풀이

이 문제는 예제를 통해 이해할 수 있다.

 

n = 2, m = 20 일 경우

• = 2^10 x 2^10
• = 2^5 x 2^5 x 2^5 x 2^5

 

n = 2, m = 9 일 경우

• = 2 x 2^8
• = 2 x 2^4 x 2^4

 

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int[] arr;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Long.parseLong(st.nextToken());
        long m = Long.parseLong(st.nextToken());

        /*
        n = 2, m = 20
        2^20 = 2^10 * 2^10 = 1024 * 1024

        n = 2, m = 27
        2^27 = 2 * 2^26 = 2 * 2^13 * 2^13
         */

        bw.write(getPow(n, m) + "");

        br.close();
        bw.flush();
        bw.close();
    }

    private static long getPow(long n, long m) {
        if(m == 0) return 1;
        else {
            if(m % 2 == 0) { // m이 짝수 일 때
                long tmp = getPow(n, m/2);
                return tmp * tmp % 10007;
            } else { // m이 홀수 일 때
                long tmp = getPow(n, m-1);
                return n * tmp % 10007;
            }
        }
    }

}