[BOJ] 1629. 곱셈

문제

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

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

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

해결 방법

접근 방식

• 2,147,483,647은 정수형의 범위 이므로 거듭제곱을 모두 하고 C로 나누면 A가 범위를 벗어난다.
• 어떻게 접근해야 할지 도저히 감이 안와서 구글링을 함
• 지수법칙과 모듈러 연산을 이용하면 된다고 한다.
• 지수 법칙:
  

  

  • 거듭제곱을 하는 방식에서 지수법칙을 이용할 수 있다.
  • 지수를 반으로 나누고 값을 두 번 곱한다
  • 이 과정을 지수가 1일 때까지 반복한다.
  • 지수가 홀수인 경우도 고려해야 한다,
  • 지수법식을 이용해서 분할이 가능하다.
• 모듈러 연산:
  

  

  • 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 나머지 연산(mod)이라고 한다.
  • 모듈러 연산의 속성에서 (a * b) mod n = ((a mod n) * (b mod n)) mod n 이 있다.
    • 지수가 홀수 일 때 temp * temp * A % C 가 아닌 ((temp * temp % C) * A) % C 를 리턴하면 된다.
    • 아직도 이해가 안됨

코드

// 곱셈, 1629
public class Week05_1629 {
    static long result;

    public static void main(String[] args) throws IOException {
        String[] input = input();
        int a = Integer.parseInt(input[0]);
        int b = Integer.parseInt(input[1]);
        int c = Integer.parseInt(input[2]);

        result = solve(a, b, c);

        output();
    }

    private static long solve(int a, int b, int c) {
        if (b == 1) {
            return a % c;
        }

        long temp = solve(a, b / 2, c);
        if (b % 2 == 0) {
            return temp * temp % c;
        } else {
            return (temp * temp % c) * a % c;
        }
    }

    private static String[] input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        return br.readLine().split(" ");
    }

    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(result + "");
        bw.flush();
        bw.close();
    }
}