백준 1629번 곱셈 Java

자연수 A를 B번 곱하고 C로 나눈 나머지를 구하는 문제이다
여기선 지수법칙과 분배법칙, int와 long 자료형의 차이를 알고있는지 확인한다.
먼저 지수법칙이란 제곱을 다룰 때 수학의 약속인데 이 문제에서 알아야할 것은
A^2n = A^n * A^n 이라는 점이다.
분배법칙이란 곱셈이나 나눗셈을 괄호 안에 수들에게 나눠줄 수 있는 성질이다.
예를 들어 {(A^n * A^n) * (A^n * A^n)} % C 라는 식이 있을 때
(A^n * A^n %C) * (A^n * A^n %C) 로 바꿔줄 수 있다.

이 두 규칙을 이해한다면 이 문제는 분할 정복 알고리즘으로 풀 수 있게된다.
만약 A = 10, B = 11, C = 12라면
10^11 % 12 = (10^5) * (10^5) * 10 % 12로 지수법칙을 이용해 쪼개고
{(10^2) * (10^2) * 10 % 12} * {(10^2) * (10^2) * 10 % 12}로 지수법칙과 분배법칙을 이용해 더 쪼개줄 수 있다. 이것을 코드로 짜면 다음과 같다.

import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class No1629 {
	
	public static final int INF = 100000000;
	
	public static long pow(long a, long b, long c) {
		if(b == 1) {
			return a%c;
		}
		long temp = pow(a,b/2,c);
		if(b%2 == 1) {
			return temp*temp%c*a%c;
		}
		return temp*temp%c;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		long a = Long.parseLong(st.nextToken());
		long b = Long.parseLong(st.nextToken());
		long c = Long.parseLong(st.nextToken());
		
		System.out.println(pow(a,b,c));
	}

}

여담으로 처음에 자료형 크기만 고려하여 A를 B번만큼 곱하면서 값이 C보다 커진다면 나머지 연산을 하면서 풀었는데 당연히 시간초과가 났다... 두 풀이의 차이라면 설명한 풀이는 둘로 쪼개면서 곱하기만 하면 되기 때문에 O(logB)인 반면 처음 풀었던 풀이는 O(B*C)이기 때문일 것이다.