[Java] 백준 #1629 (분할정복)

📍 출처

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

📝 문제

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

⌨️ 입력

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

🖨 출력

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

⌨️ 예제 입력

10 11 12

🖨 예제 출력

4

📚 내가 제출한 코드

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

public class Main {
    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());

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        System.out.println(pow(A,B));
    }

    public static long pow(int a, int b){
        if(b == 1){
            return a % C;
        }

        long temp = pow(a, b / 2);

        if(b % 2 == 1){
            return (((temp * temp) % C) * (a % C)) % C; // (A * B) % C == (A % C * B % C) % C
        }else{
            return temp * temp % C;
        }
    }
}

*✏️ 내가 제출한 코드에 대한 설명

• 모듈러의 합동공식을 알아야 풀 수 있다. (A X B) % C == (A % C X B % C) % C