백준 2981번 "검문"

문제

백준 2981번 검문

풀이

오름차순의 입력값 a, b를 받았을 때, a와 b의 최소공약수에 관한 식을 정리하면 다음과 같다.

이걸로 b-a는 a, b의 최소공약수의 배수라는 것을 알 수 있다.

또한 같은 나머지 R을 가지게 하는 숫자 M에 대한 정리를 하면 다음과 같다.

b-a가 a, b의 최대공약수 배수이기 때문에 M이 a, b의 최대공약수의 배수/약수임을 알 수 있다.

즉, 입력받은 수들을 오름차순으로 정렬하고, 인접한 수의 차들의 최대공약수를 구한 후, 그 수의 약수를 구하면 된다.

Python 코드

import sys
import math
input = sys.stdin.readline

n = int(input())
num = []
for _ in range(n):
  num.append(int(input()))

num.sort()

arr = []
for i in range(1, n):
  arr.append(num[i]-num[i-1])

tmp = arr[0]
for i in range(len(arr)):
  tmp = math.gcd(tmp, arr[i])

ans = [tmp]
for i in range(2, int(tmp**0.5)+1):
  if tmp % i == 0:
    ans.append(i)
    ans.append(tmp//i)

ans.sort()
ans = list(set(ans))

for x in ans:
  print(x, end=' ')