백준 1629 곱셈 Java: 빠른 거듭제곱과 모듈러 연산

백준 1629 곱셈 Java 풀이는 A^B를 직접 계산하지 않고 exponent를 절반씩 줄이는 빠른 거듭제곱을 사용한다. 처음 풀었을 때는 32분 동안 반복문과 재귀 두 방식을 모두 적어 보았다. 다만 두 method를 같은 signature로 한 class에 붙인 메모는 그대로는 컴파일되지 않는다. 여기서는 흐름을 한눈에 추적하기 쉬운 반복문 하나로 정리했다.

큰 거듭제곱을 그대로 계산하면 안 되는 이유

A^B mod C에서 B는 매우 클 수 있다. A를 B번 곱하면 시간 복잡도가 O(B)이고, 나머지를 마지막에 한 번만 계산하면 중간값이 자료형 범위를 훨씬 넘어선다.

모듈러 곱셈은 다음 성질을 이용할 수 있다.

(x * y) mod C = ((x mod C) * (y mod C)) mod C

따라서 곱할 때마다 나머지를 취하면 중간값을 제한할 수 있다. 남은 문제는 곱셈 횟수다.

exponent의 binary bit를 읽는다

예를 들어 A^11에서 11 = 1011₂다.

A^11 = A^8 * A^2 * A^1

현재 exponent의 가장 낮은 bit가 1이면 현재 base를 답에 곱한다. 매 단계마다 base를 제곱하고 exponent를 오른쪽으로 한 bit 이동한다.

exponent	low bit	result에 곱할 값	다음 base
11	1	A	A²
5	1	A²	A⁴
2	0	없음	A⁸
1	1	A⁸	A¹⁶

exponent가 매번 절반이 되므로 반복 횟수는 O(log B)다.

Java 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        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(modPow(a, b, c));
    }

    private static long modPow(long base, long exponent, long modulus) {
        long result = 1 % modulus;
        base %= modulus;

        while (exponent > 0) {
            if ((exponent & 1L) == 1L) {
                result = (result * base) % modulus;
            }

            base = (base * base) % modulus;
            exponent >>= 1;
        }

        return result;
    }
}

result를 1 % modulus로 시작하면 C = 1인 경계에서도 답이 0이 된다. 이 문제에는 modular division이 없으므로 Fermat's little theorem이나 modular inverse를 끌어올 필요도 없다.

예제로 확인하기

입력:

10 11 12

출력:

4

10^11 전체를 만들지 않고 매 곱셈 직후 % 12를 적용해 같은 나머지를 얻는다.

복잡도와 overflow

• 시간 복잡도: O(log B)
• 추가 공간 복잡도: O(1)
• 자료형: 입력을 long으로 받고 곱셈도 long에서 수행한다.

문제의 A, B, C 상한은 signed 32-bit 범위다. % C를 적용한 두 값의 곱은 (C - 1)^2보다 작아 long 범위 안에 들어간다. 입력 범위가 long 전체로 넓어지는 별도 문제라면 단순한 long * long도 overflow할 수 있으므로 곱셈 자체를 안전하게 구현해야 한다.

exponent를 bit로 읽는 배경은 비트 연산과 2의 보수, Java 기본 범위를 넘어서는 정수 계산은 무한히 큰 수의 사칙연산에서 이어서 볼 수 있다.

참고 자료

• 백준 1629: 곱셈
• Internet Archive: 백준 1629 문제 스냅샷
• Java Language Specification 21: Shift Operators