백준 2981 검문 Java: 차이의 GCD와 약수 오름차순 출력

백준 2981번 ‘검문’은 여러 수를 어떤 M > 1로 나눴을 때 나머지가 모두 같아지는 모든 M을 오름차순으로 출력한다. 핵심은 두 수의 차이는 M으로 나누어떨어진다는 식을 세우는 것이다.

• 백준 2981번 검문

같은 나머지를 식으로 없애기

두 수 A와 B를 M으로 나눈 나머지가 모두 r이라고 하자.

A = aM + r
B = bM + r
A - B = (a - b)M

따라서 M은 |A-B|의 약수다. 수가 여러 개라면 모든 인접 차이를 나누어야 하므로, 정렬한 뒤 차이들의 최대공약수 G를 구한다. 답은 G의 약수 중 1보다 큰 모든 수다.

인접 차이만 사용해도 충분하다. 임의의 두 수 차이는 그 사이 인접 차이들의 합이므로, 모든 인접 차이를 나누는 M은 모든 쌍의 차이도 나눈다.

약수를 정렬 없이 오름차순으로 모으기

G의 약수는 d와 G/d가 쌍을 이룬다. d를 2부터 √G까지 증가시키면 작은 약수는 이미 오름차순이고, 큰 약수는 내림차순으로 발견된다.

• 작은 약수는 low에 그대로 저장
• 짝이 되는 큰 약수는 high에 저장한 뒤 역순 출력
• 마지막에 G 자체를 출력

제곱수에서는 d == G/d를 한 번만 넣는다.

Java 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    private static int gcd(int left, int right) {
        while (right != 0) {
            int remainder = left % right;
            left = right;
            right = remainder;
        }
        return Math.abs(left);
    }

    private static void append(StringBuilder output, int value) {
        if (output.length() > 0) {
            output.append(' ');
        }
        output.append(value);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        int count = Integer.parseInt(reader.readLine());
        int[] numbers = new int[count];

        for (int index = 0; index < count; index++) {
            numbers[index] = Integer.parseInt(reader.readLine());
        }

        Arrays.sort(numbers);

        int differenceGcd = numbers[1] - numbers[0];
        for (int index = 2; index < count; index++) {
            differenceGcd = gcd(
                    differenceGcd,
                    numbers[index] - numbers[index - 1]
            );
        }

        List<Integer> low = new ArrayList<>();
        List<Integer> high = new ArrayList<>();

        for (
                int divisor = 2;
                (long) divisor * divisor <= differenceGcd;
                divisor++
        ) {
            if (differenceGcd % divisor != 0) {
                continue;
            }

            low.add(divisor);
            if ((long) divisor * divisor != differenceGcd) {
                high.add(differenceGcd / divisor);
            }
        }

        StringBuilder output = new StringBuilder();
        for (int divisor : low) {
            append(output, divisor);
        }
        for (int index = high.size() - 1; index >= 0; index--) {
            append(output, high.get(index));
        }
        append(output, differenceGcd);

        System.out.println(output);
    }
}

문제는 서로 다른 수가 주어진다고 보장하므로 정렬 후 첫 차이는 0보다 크다. 약수 탐색은 O(√G), 정렬은 O(N log N), GCD 계산은 차이마다 logarithmic time이 든다.

15분 고민한 뒤 검색에서 배운 것

원문에는 약 15분 고민한 뒤 검색했고, 같은 나머지를 식에서 소거해 차이의 GCD로 바꾸는 유도를 배웠다고 적혀 있다. 처음 code는 2부터 G까지 모든 수를 확인해 약 1540ms가 기록됐고, 다른 제출자의 C++ code에서 약수 쌍을 이용한 출력 방식을 보고 Java로 옮긴 뒤 76ms를 기록했다.

두 수치는 통제된 benchmark가 아니므로 일반적인 Java·C++ 성능 비교로 읽으면 안 된다. 남길 만한 학습은 O(G) 약수 탐색을 O(√G)로 줄이고, 작은 약수와 큰 약수의 발견 순서를 이용해 별도 정렬까지 생략한 방법이다.

유클리드 알고리즘으로 분수를 약분하는 예시는 백준 3036 링, prime factor exponent를 세는 문제는 백준 2004 조합 0의 개수에서 이어진다.

검증 범위

Java source를 수동 검토하고 G가 prime·perfect square·여러 약수를 가진 경우와 작은 random distinct number set을 모든 M을 직접 시험하는 oracle과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.