[JAVA] 백준 - 검문 2981 (정수론, 유클리드 호제법)

https://www.acmicpc.net/problem/2981

2981번: 검문

 

이 문제는 정말 수학문제였습니다.

정답률이 21프로 밖에 안되는데 그 이유는 완전 탐색의 경우 시간초과가 나기 때문입니다.

 

최악의 경우를 생각해보자. 먼저 M의 범위를 알아야합니다.

결론부터 이야기하면 M은 1보다 큰수이며 주어진 N개의 수 중에서 가장 큰수보다 작은 수입니다.

예를 들어, 주어진 수가 2, 3, 8 ,15 라면 M 의 범위는 2~14 입니다.

왜냐하면 M이 가장 큰 수라고 가정 해보면 주어진 수에서 하나는 나머지가 반드시 0이지만 나머지 수들은 전부 다른 수라고 가정이 되어있으므로 0이 아닌 다른 값이 반드시 존재합니다.

 

따라서 최악의 경우 M 은 999999999 까지 순차 탐색을 해야하고 100개의 수에 대해서 진행해야 하므로 1초안에 진행하는 것은 불가능합니다.

 

수학적으로 접근해야 합니다. 

 

만약 2개의 수가 있다고 가정 했을 때 M 값은 어떻게 구할 수 있을까요?

여기 A 와 B 라는 수가 있다고 해봅시다.

 

A = aM + R ( a는 임의의 자연수 , R 은 나머지)
B = bM + R ( b는 임의의 자연수 , R 은 나머지)

A 에서 B 를 빼봅니다.

A-B = (a-b)M

따라서 M 은 A-B 의 2이상 약수들입니다. 왜냐하면 M은 2이상의 자연수이므로 a-b 또한 자연수여야합니다. 예를 들어 A = 20 이고 B = 10 이라면  A-B = 10 이므로 M 은 10의 약수입니다. 이를 풀어보면 다음과 같습니다.

A-B = (a-b)*M 
    = 1 * 10
    = 2 * 5
    = 5 * 2
    = 10 * 1

M = 2,5,10 입니다.

 

3개 이상의 수들에 대해서는 어떨까요?

 

A = aM + R
B = bM + R
C = cM + R

A-B = (a-b)M
B-C = (b-c)M

a,b,c 는 2개의 수에서 보여줬던 예처럼 똑같은 가정을 했다고 칩시다. 여기서 M 은 A-B 와 B-C의 최대공약수의 약수들입니다.

이해가 안되시면 예를 들어서 설명해보겠습니다.

 

10 = (a-b)*M 

20 = (b-c)*M 

 

이라고 해봅시다. M 은 10의 약수이기도 하면서 20의 약수입니다.

M = 2 라고 하면 

 

10 = 5 * 2

20 = 10 * 2 

 

입니다. 가장 큰 M은 무엇일까요? 최대공약수로서 10입니다.

M 은 10보다 클 수 없습니다.

 

이제 3개가 아닌 N 개로 확장해봅니다. A,B,C 로 시작하는 것이 아니라 

A1,A2, ... An 으로 식을 세워 보겠습니다.

 

A1 = a1*M + R
A2 = a2*M + R
A3 = a3*M + R
...
An = an*M + R

A1-A2 = (a1-a2)*M
A2-A3 = (a2-a3)*M
..
An-1 - An = (an-1 - an )*M

// M 은 A1-A2, A2-A3, ... An-1 - An 의 최대공약수들의 약수!

위 식을 코드로 나타내면 다음과 같습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
 * Main 설명 : 검문
 * @author jwonjun
 * @version 1.0.0
 * 작성일 : 2022/03/29
**/
public class Main {
    static Fs fs = new Fs();

    public static void main(String[] args) throws Exception{
        int n = fs.nInt();

        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = fs.nInt();
        }

        // 오름차순 정렬
        Arrays.sort(arr);

        /**
         *
         * A = aM + r , B = bM + r , C = cM + r
         * 일때 , A-B = (a-b)M
         * B-C = (b-c)M
         * 이때 M 은 A-B 와 B-C의 최대 공약수임. (단 , M != 1)
         *
         */

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

        System.out.println(make(v));



    }

    static StringBuilder make(int v) {
        StringBuilder sb = new StringBuilder();

        for(int i=2;i<=v/2;i++) {
            if(v%i==0) sb.append(i).append(" ");
        }
        sb.append(v).append("\n");

        return sb;
    }

    static int gcd(int a,int b) {
        if(a%b==0) return b;
        return gcd(b,a%b);
    }

    static class Fs{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        public int nInt() throws Exception{
            if(!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
            return Integer.parseInt(st.nextToken());
        }
    }
}