[백준] 1629번 곱셈

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

1629번: 곱셈

 

 

문제는 간단하다. 

자연수 A의 B 승을 C 로 나눈 나머지를 구하는 문제. 

 

다만 B의 크기가 매우 크기 때문에 일일이 구하기에는 시간초과가 발생한다. 

 

 

여기서 지수법칙이 사용되는데, 

 

A^2 * A^2 = A^4 의 값이 된다. 

 

분할 정복 방법을 사용하여 B 의 크기를 2 로 계속 나누어 값을 구하고

구한 값끼리 곱한다면 A 의 B 승 값을 구할 수 있다.

public class Main {
    static long C;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] tmp = reader.readLine().split(" ");
        
        long a = Long.parseLong(tmp[0]);
        long b = Long.parseLong(tmp[1]);
         C = Long.parseLong(tmp[2]);
        // a^n = a^n/2 * a^n/2
        
        System.out.println(pow(a, b));
    }
    
    public static long pow(long a, long b) {
        if (b == 1) {
            return a % C;
        }
        
        long result = pow(a, b/2);
        
        if (b % 2 == 1) {
            return ( result * result % C) * a % C;
        }
        
        return result * result % C;
    }
}