[백준] 1629 곱셈 [자바]

 

 

---

 

https://st-lab.tistory.com/237

[백준] 1629번 : 곱셈 - JAVA [자바]

 

 

---

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

public class Main {
	static long dp[];
	static int A,B,C;
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 		A = Integer.parseInt(st.nextToken());
 		B = Integer.parseInt(st.nextToken());
 		C = Integer.parseInt(st.nextToken());
 		dp = new long[3];
 		dp[1] = A % C;
 		dp[2] = dp[1]*A%C; //A * A 로하면 오버플로우 발생
 		System.out.println(divide(B));
 	}
 	static long divide(int b) {
 		if(b <= 2) {
 			return dp[b];
 		}
 		long mid = divide(b/2);
 		
 		if(b % 2 == 1) {
 			return (mid * mid % C) * A % C;
 		}
 		else {
 			return mid*mid%C;
 		}
 	}
}