[백준] 1629번 곱셈 - JAVA 풀이

숫자가 커지지 않도록 처리가 필요하다.
위 문제를 보고 들었던 생각은 다음과 같다.
 
1. 제곱을 계속하게 될 경우 숫자가 너무 커져서 INT 크기를 넘어간다.
따라서, 이에 대한 처리가 필요하다.
2. 규칙성이 있을 것 같다.

위 두가지 였다.
규칙성을 찾아보기 위해서 다음과 같이 제곱을 계속 해보았다.

위처럼 결과가 나왔다. 결과값을 13의 곱 + 나머지로 표현해보았다.
 

위처럼 표현해보면서 어떤식으로 처리해주어야할지 보였다.
예를 들어, 5의 세제곱의 13의곱 +나머지를 보게되면
5의 제곱의 13의곱 +나머지로 표현한 식에 각각 5를 곱한것이다.
 
그런데 이미 몫부분은 13으로 나누어떨어지는 값에 5를 곱한것이기 때문에 무조건 13으로 나누어 떨어지므로 고려할 필요가 없고 따라서 나머지에 5를 곱한값의 나머지만 계속해서 확인하면서 곱해가면 된다는 규칙성을 찾았다.
 
(위 규칙성까지 찾고 다른분들의 풀이 방법을 찾고하였다.)
 

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

public class Main {
	
	static long A;
	static long B;
	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());
		A = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		long result = func(A,B,C);
		System.out.println(result);

	}

	public static long func(long a, long b, long c) {
		if(b==0) {
			return 1;
		}
		if(b%2 == 1) {
			return (a * (func(a,b-1,c))) % c;
		}
		long k = func(a,b/2,c);
		return (k*k)%c;
	}
}