P.1629 곱셈

코드

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

public class P_1629 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        long a = arr[0], b = arr[1], c = arr[2];

        long result = Power(a, b, c);

        bw.write(Long.toString(result));
        bw.flush();
    }

    private static long Power(long a, long b, long c) {
        if (a == 0) return 0;
        if (b == 0) return 1;
        if (b == 1) return a % c;

        long divide = Power(a, b / 2, c);

        if (b % 2 == 0) {
            return (divide * divide) % c;
        }
        else {
            return (divide * divide % c) * a % c;
        }
    }
}

코드 설명

문제 조건이 0.5초이기 때문에 반복문으로 풀게 되면 무조건 시간 초과가 나는 문제다.

최대 연산 횟수가 2147483647, 코드에 따라서 2147483646이기 때문에 O(logn)으로 풀 경우 시간 제한 안에 풀 수 있게 된다.

O(log n)의 경우 분할 정복 밖에 없기에 분할 정복으로 풀면 된다.

 

곱셈 법칙을 이용하면 쉽게 풀 수 있다.

 

위 사진은 각각 지수가 짝수, 홀수일 때 곱셈법칙에 해당한다.

짝수의 경우 지수 / 2를 한 값을 곱해주고, 홀수의 경우 지수 / 2를 한 값을 곱한 후, 밑을 곱해준다.