[백준 1629] 곱셈 (JAVA)

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

1629번: 곱셈

 

Math.pow로 하면 시간초과가 발생한다...

분할 정복을 이용하여 문제를 해결할 수 있다!

예를 들어,

다섯제곱수이면 

5 -> 2 *2 *1 ->1*1*1*1*1 이다!

네제곱수이면

4->2*2->1*1*1*1이다!

 

 

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

public class Main {
	static long c;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		long n= Integer.parseInt(st.nextToken());
		long b= Integer.parseInt(st.nextToken());
		c= Integer.parseInt(st.nextToken());
		
		System.out.println(pow(n,b));
		
	}
	static public long pow(long n,long b) {
		if(b==1) {
			return n%c;
		}
		
		long temp= pow(n,b/2);
		if(b%2==1) {
			return temp*temp%c*n%c;
		}
		else {
			return temp*temp%c;
		}
	}

}