[KOITP] 거듭제곱 구하기

출    처 : http://koitp.org/problem/SDS_PRO_7_5/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	2242	351 (16%)	291

문제

정수 a와 m이 주어 졌을때, a의 m 거듭제곱을 1,000,000,007 로 나눈 나머지를 출력하는 문제이다.

입력

두 정수 a와 m이 주어진다. 1 <= a, m <= 2^63 - 1

출력

a 의 m 제곱 값을 10억 7로 나눈 나머지를 출력한다.

힌트

예제 입력

2 4

예제 출력

16

< Comment >

 굉장히 쉬운 문제인데 모듈 연산에 대해 잘 모르고 있다보니 쓸데없이 오랜 시간이 걸렸습니다. 기본적으로 모듈 연산이 되어있는 값을 Recursive 함수의 리턴값으로 두고, 이를 곱하고 다시 여기에 모듈 연산을 해 주는 식으로 진행했습니다 .입력받는 a의 값이 매우 클수도 있으므로, 여기도 모듈 연산을 해 주면, 값 출력이 정상적으로 이루어집니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Power {
	
	public static long MOD = 1000000007;
	
	public static long a = 0;
	public static long m = 0;
	
	public static long cache[] = new long[64];
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		a = Long.parseLong(st.nextToken()) % MOD;
		m = Long.parseLong(st.nextToken());
		
		long answer = power(a, m);
		bw.write("" + answer);
		bw.flush();
		bw.close();
	}
	
	public static long power(long aa, long mm) {
		
		if (mm == 0)	return 1;
		
		long newa = power(aa, mm/2);
		if(mm % 2 == 0) {
			return (newa * newa) % MOD;
		} else {
			return ((aa % MOD) * ((newa * newa) % MOD)) % MOD;
		}
	}
}