[백준] 2981번: 검문

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

2981번: 검문

 

5, 14를 예시를 들어보자. M이 나누는 숫자고(ex. 3), DIV는 나머지(ex. 2)라고 했을 때, 다음과 같이 표현할 수 있다.

5 = t0*M + DIV
14 = t1*M + DIV

(5 = 1*3 + 2, 14 = 4*3 + 2가 그 예시다.)

 

위 식으로 다음을 도출해낼 수 있다.

9 = (t1 - t0)*M

(9 = (4 - 1)*3이 그 예시다.)

우리는 여기서 M의 경우의 수를 찾아내야한다. 여기서 t1, t0는 임의의 수이므로, M은 9의 약수가 된다. 즉, 5와 14의 경우에는 {1, 3, 9}가 성립하는 모든 경우의 수다.

 

결국 우리가 해야할 것은, 입력받은 모든 수들에 대해 이러한 과정(두 값의 차이에 대해 약수를 구하는 것)을 거쳐 M의 후보를 구한 뒤, 공통되는 것을 찾아내는 것이다. 다음은 예제 입력 2를 오름차순으로 정렬(5, 14, 17, 23, 83)한 뒤 각각 (14 - 5), (17 - 14), ..., (83 - 23)에 대해 약수를 구한 결과이다. 1은 문제의 조건에 의해 배제되므로 삭제해주었다.

처음에는 결과를 도출하기 위해 set의 intersection을 사용하여서 풀었다. 이것으로도 문제가 풀리긴 하지만 더 빠른 풀이가 있다.

그것은 바로 최대공약수를 이용하는 것이다. 두 값의 차이값들(위 사진에선 9, 3, 6, 60)의 최대공약수(3)을 구한 뒤, 그 값의 약수를 구하는 것이다.

예제 입력 1의 경우에는 4가 그 최대공약수이며, {2, 4}가 정답이다.

 

import sys
input = sys.stdin.readline


def get_measures(n):
    res = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            res.add(i)
            res.add(n//i)

    res.remove(1)

    return res


def gcd(x, y):
    if y != 0:
        return gcd(y, x % y)
    else:
        return x


if __name__ == '__main__':
    N = int(input())
    nums = list(int(input()) for _ in range(N))
    nums.sort()

    g = nums[1] - nums[0]
    for i in range(1, N-1):
        g = gcd(g, nums[i+1] - nums[i])

    print(*sorted(list(get_measures(g))))