[백준] 2619 곱셈

문제보기

언제쯤 분할정복과 친해질 수 있을까?ㅠㅠ

문제의 핵심은 이렇다.
당연히 O(B)로 했다가는 터지도록 되어있기 때문에…
a^2b = a^b * a^b 혹은 a^2b+1 = a * a^2b 이렇게 나눠서 계산해주면 된다. 절반씩만 계산하므로 O(logN)의 시간복잡도로 계산할 수 있다.

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

class Main{
	
	static int ip(String s){ return Integer.parseInt(s); };
	
	static int a;
	static int b;
	static int c;
	
	// a ^ cnt 를 반환하는 함수 
	static long go(int cnt) {
	
		if(cnt == 1) { // 1승일땐 그냥 a만 반환한다(c로 꼭 나눠야함에 유의)
			return a%c;
		}

		if(cnt%2 == 0) { // 짝수승 일때는 
			long temp = go(cnt/2)%c; 
			return temp*temp%c; // 반쪽만 구해서 제곱해주면 된다 
		}else { // 홀수승 일때는 
			return a*go(cnt-1)%c; // cnt-1 승에 a 만 한개 더 곱해주자 
		}
	}

	
     public static void main(String[] args) throws IOException{
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(br.readLine());
         a = ip(st.nextToken());
         b = ip(st.nextToken());
         c = ip(st.nextToken());
         
         System.out.println(go(b));

     }
}