문제

이해

간단한 문제이다. 2147483647 이하의 자연수 A, B, C가 주어진다.

A를 B번 곱한 수를 C로 나는 나머지를 출력한다.

접근

문제의 쟁점은 두 가지이다. 첫째는 계산과정에서 int 범위에 벗어날 수 있다는 것이고, 둘째는 연산횟수인 B가 최댓값일때 시간초과가 발생할 수 있다는 것이다.

첫째는 단순하게 자료형을 int대신 long을 활용하면 해결할 수 있다.

문제는 둘째인데, 이는 나머지 연산의 분배법칙을 이용하면 해결할 수 있다.

$A^B$ % $C$ = $(A * A * A * A...)$ % $C$ 는 분배법칙에 의해 (A % C * A % C ...) 로 나타낼 수 있다.

그렇다면 이를 활용해 연산횟수를 줄일 수 있지 않을까?

$A^B = (A*A)^(B/2)$ 로도 표현할 수 있다. 다시 말해 제곱수를 반으로 줄이고 A를 제곱하는 것이다.

단, B가 홀수인 경우에는 2로 나누어떨어지지 않기 때문에 A를 하나 가져와서 따로 연산에 포함시킨다.

위와 같은 과정을 반복문을 통해 수행하고 B가 1이 되는 경우 연산을 한번만 수행하면 되기 때문에 종료한다.

반복과정에서 따로 빼낸 수들과 최종 결과로 계산된 수를 곱하여 나머지를 연산하면 최종 값이 나오게 된다.

나머지 연산은 분배법칙을 통해 A*A가 C보다 크다면 이의 나머지로 치환가능하다.

코드

package java_baekjoon;

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

public class prob1629 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        long A = Integer.parseInt(st.nextToken());
        long B = Integer.parseInt(st.nextToken());
        long C = Integer.parseInt(st.nextToken());
        long ans = 1;

        if (A > C) { //분배법칙 (나머지끼리 연산해도 결과는 같음)
            A = A % C;
        }

        while (true) {
            if (B == 1) { //B가 1이면 반복종료
                break;
            }

            if (B % 2 == 1) { //B가 홀수라면 따로 A를 빼내고 짝수로 변환해야함
                ans = (ans * A) % C; //분배법칙
                B--;
            }
            A = (A * A) % C; //지수를 줄이는 과정, 분배법칙
            B /= 2;
        }

        ans = (ans * A) % C; //분배법칙

        System.out.println(ans);
    }
}

글로 설명하기 조금 어려운 문제인 것 같다. 마크다운으로 수식을 작성하기도 힘들어서 코드를 참고하면 좋을듯하다.

결과