<BOJ>1629번: 곱셈

문제

1629번: 곱셈

접근

• 지수 법칙과 모듈러 성질을 알고 있으면 쉽게 풀린다.

  a^n * a^m = a^(n+m)
  (a * b) % c = (a % c * b % c) % c

• 지수를 반으로 나누는 방식으로 지수 법칙을 적용하자.
• 지수가 홀수인 경우와 짝수인 경우를 나눠서 생각한다.

내 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        long c = Long.parseLong(st.nextToken());

        System.out.println(solution(a, b, c));
    }

    public static long solution(long a, long b, long c) {
        if (b == 1) return a % c;
        long val =  solution(a, b/2, c);
        val = val * val % c;
        if (b % 2 == 0) return val;
        return val * a % c;
    }
}

포스팅을 작성하며 다시 풀어봤는데도 조금 헷갈린다.
분할 정복의 관점에서 간단하게 생각하도록 해보자.