검문

출처 : 백준 #2981

시간 제한	메모리 제한
1초	128MB

---

문제

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.

먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

---

입력

첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)

다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다.

항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

---

출력

첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다. 이때, M은 증가하는 순서이어야 한다.

---

입출력 예시

예제 입력 1

3
6
34
38

예제 출력 1

2 4

---

예제 입력 2

5
5
17
23
14
83

예제 출력 2

3

---

풀이

생각 및 풀이 설명

• 수학적으로 접근해야 풀 수 있는 문제이다.
  • A = a*G + r
  • B = b*G + r
  • |A - B| = |(a-b)*G|
  • 이렇게 두 수의 차의 최대 공약수에 대한 공약수를 구하게 되면 나누었을 때 나머지가 같은 수를 찾을 수 있게 된다.
• 최대공약수를 구하는 방법 (유클리드 호제법)
  • 두 정수 a,b에 대해서 a>b일 때, a=bq+r이라 하면 gcd(a,b) = gcd(b,r)이다. (단 0<=r)

# 최대 공약수 구하기(유클리드 호제법)
while arr:
    a = arr.popleft()
    if len(arr) > 0:
        b = arr.popleft()
        while a % b != 0:
            a, b = b, a % b
        arr.appendleft(b)
    else:
        result.append(a)

• 공약수를 구하는 방법 (시간복잡도 낮추기)
  • "임의의 자연수 N의 약수들 중에서 두 약수의 곱이 N이 되는 약수 A와 약수 B는 반드시 존재한다"는 규칙이 존재하기 때문에, 자연수 N의 제곱근까지의 약수를 구하면 그 짝이 되는 약수는 자동으로 구해진다. (i, n//i)
  • O(N^(1/2))의 시간복잡도를 가진다.

# 최대 공약수의 약수 구하기
while result:
    r = result.pop()
    for i in range(1, int(r**(1/2))+1):
        if r % i == 0 and i not in answer:
            answer.append(i)
            if i != (r//i):
                answer.append(r//i)

python code

# 백준 2981번 검문
from sys import stdin
from collections import deque
input = stdin.readline
n = int(input())
numbers = []
for _ in range(n):
    numbers.append(int(input()))

numbers.sort(reverse=True)  # 내림차순 정렬
arr = deque()
for i in range(len(numbers)-1):
    temp = abs(numbers[i] - numbers[i+1])
    arr.append(temp)

result = []
# 최대 공약수 구하기(유클리드 호제법)
while arr:
    a = arr.popleft()
    if len(arr) > 0:
        b = arr.popleft()
        while a % b != 0:
            a, b = b, a % b
        arr.appendleft(b)
    else:
        result.append(a)

answer = []
# 최대 공약수의 약수 구하기
while result:
    r = result.pop()
    for i in range(1, int(r**(1/2))+1):
        if r % i == 0 and i not in answer:
            answer.append(i)
            if i != (r//i):
                answer.append(r//i)

answer.sort()
answer.pop(0)   # 1 빼기
for i in range(len(answer)-1):
    print(answer[i], end=" ")
print(answer[-1])