[Algorithm] 백준/1629 :: 곱셈

* 핵심

Divide and Conquer 사용하여 시간 복잡도 줄이는 방식

10^11 = 10 * 10^5 * 10*5 이고, 10^5 = 10 * 10^2 * 10^2 라는 개념을 이용

* 문제

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

* 소스 코드

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
 
        int a = Integer.parseInt(stk.nextToken());
        int b = Integer.parseInt(stk.nextToken());
        int c = Integer.parseInt(stk.nextToken());
 
        long ans = DivideConquer(a, b, c);
        System.out.println(ans);
    }
 
    public static long DivideConquer(int a, int b, int c) {
        if (b == 0) return 1;       //종료 조건
        if (b % 2 == 1) {           //지수가 홀수인 경우
            return DivideConquer(a, b - 1, c) * a % c;
        } else {                    //지수가 홀수인 경우
            long v = DivideConquer(a, b / 2, c) % c;
            return v * v % c;
        }
    }
}