문제

아이디어

문제를 일반화해보자. 설명이 쉽도록 세 요소를 가지는 배열을 만들어보자.

A[0] = A, A[1] = A + d1, A[2] = A + d2

d1, d2가 자연수라고 가정한다면 배열 A는 오름차순 정렬되어 있음을 알 수 있다.
이 때, A[0], A[1], M과의 관계는 아래와 같다.

A % M = (A + d1) % M 이며,
이는 모듈러 연산의 성질에 의해 A % M = ((A % M) + (d1 % M)) % M로 나타낼 수 있다.

이 때 d1 % M은 반드시 0이어야 한다. 즉, d1은 0 혹은 M의 배수임을 알 수 있다.
또한 같은 수가 두 번 이상 주어지지 않는다는 조건에 의해 d1은 M의 배수로 조건을 좁힐 수 있다.
같은 논리에 의해 d2 또한 M의 배수임을 알 수 있고, 더 나아가 배열의 모든 요소와 배열의 최솟값의 차 또한 M의 배수이다.
다시 말해 M은 배열 A가 오름차순 정렬되어 있을 때 모든 A[i] - A[0] (i != 0)의 공약수이다.

유클리드 호제법을 사용해 최대공약수를 구하고, 이 최대공약수의 약수들을 출력한다면 풀어낼 수 있겠다.
이 때, 문제의 조건에 의해 M != 1임에 유의하자.

소스코드

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

public class Main {
    static int N;
    static int[] arr;

    static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

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

        N = Integer.parseInt(br.readLine());
        arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);

        int m = arr[1] - arr[0];
        for (int i = 2; i < N; i++) {
            m = gcd(arr[i] - arr[0], m);
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 2; i * i <= m; i++) {
            if (m % i == 0) {
                pq.add(i);
                if (i != m / i)
                    pq.add(m / i);
            }
        }
        pq.add(m);

        StringBuilder ans = new StringBuilder();
        while (!pq.isEmpty()) {
            ans.append(pq.poll()).append(' ');
        }
        System.out.println(ans);
    }
}

채점결과

출력값을 정렬하지 않아 틀렸다.
정답률이 20%대로 까다로운 문제였지만 초반 방향을 잘 잡아 나가 수월하게 풀 수 있었다.