곱셈

문제

1629번: 곱셈

문제 설명

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

제한 사항

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

입출력 예

입력	출력
10 11 12	4

입출력 예 설명

아이디어

분할 정복

제출 코드

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

public class one1629 {
    private int a;
    private int b;
    private int c;

    public void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer infoToken = new StringTokenizer(reader.readLine());
        a = Integer.parseInt(infoToken.nextToken());
        b = Integer.parseInt(infoToken.nextToken());
        c = Integer.parseInt(infoToken.nextToken());

        System.out.println(calculation(b));
    }

    // a % c 연산이 b 번 반복되어야 한다는 점을 기억
    public long calculation(int b) {
        if (b == 1) {
            return a % c;
        }

        long half = calculation(b / 2);
        if (b % 2 == 1) {
            return half * half % c * a % c;
        }
        else {
            return half * half % c;
        }
    }

    public static void main(String[] args) throws IOException {
        new one1629().solution();
    }
}