백준|1629번|곱셈

문제설명
자연수 A, B, C를 입력받고 A의 B 제곱을 C로 나눈 나머지를 구하는 문제입니다.

작동 순서
1. 자연수 A, B, C를 입력받습니다.
2. B가 2의 배수일 경우 ((A(B/2)%C)*(A(B/2)%C))(분할정복)를 반환합니다.
3. B가 2의 배수가 아닌 경우 ((A(B/2)%C)*(A(B/2)%C)*A%C)를 반환합니다.
4. 연산결과를 memo에 저장을 하고 같은 값을 다시 불러와야할 경우 똑같은 계산을 다시 수행하지않고 memo에 저장되어 있는 값을 가져옵니다.
5. 연산을 한 뒤 연산 결과를 출력합니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class 백준_1629번_곱셈 {
    static Map<Long, Long> memo = new HashMap<>();
    static long power(long A, long B, long C){
        if(B==1) return A%C;
        else if(B>=2){
            if (B%2 == 0) {
                if (!memo.containsKey(B/2)){
                    memo.put(B/2, power(A%C, B/2, C)%C);
                }
                return (memo.get(B/2) * memo.get(B/2))%C;
            }
            else {
                if (!memo.containsKey(B/2)){
                    memo.put(B/2, power(A%C, B/2, C)%C);
                }
                return ((memo.get(B/2) * memo.get(B/2) % C) * A%C)%C;
            }
        }
        else return 1;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int A = Integer.parseInt(input[0]), B = Integer.parseInt(input[1]), C = Integer.parseInt(input[2]);
        System.out.print(power(A,B,C));
    }
}