백준|2981번|검문

문제설명
수들을 입력받고 그 수들을 나누었을 때 나머지가 모두 같아지는 숫자들을 찾아서 출력하는 문제입니다.

작동 순서
1. 숫자들을 입력받습니다.
2. 숫자들을 정렬한 후 각 자릿수들간의 차이를 저장합니다.
3. 유클리드 호제법에서 A, B, C, D를 나머지가 같게 만드는 수를 구하기 위해서는 A-B, B-C, C-D의 공약수를 구하면 되므로 각 자릿수들의 차이의 공약수를 구해줍니다.
4. 최대공약수의 약수들을 모두 구합니다.
5. 최대공약수의 약수들을 출력합니다.

소스코드

import sys


def gcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a


n = int(sys.stdin.readline())
m = []
diff = []
result = []
for i in range(n):
    m.append(int(sys.stdin.readline()))

m.sort()

for i in range(1, n):
    diff.append(m[i]-m[i-1])

prev = diff[0]
for i in range(1, n-1):
    prev = gcd(prev, diff[i])

for i in range(2, int(prev**(1/2))+1):
    if prev % i == 0:
        result.append(i)
length = len(result)
for i in range(length-1, -1, -1):
    if prev / result[i] != result[i]:
        result.append(int(prev/result[i]))
result.append(prev)

for i in range(len(result)):
    print(result[i], end=" ")

후기
어려운 수학적 공식이 필요한 문제에다가 최대공약수의 약수를 구할 때도 그냥 단순하게 구했더니 시간초과가 나서 좀 고생을 했습니다. 수학공부를 좀더 해야 할 것 같고 코드를 좀 더 깔끔하게 작성하는 법도 공부해야 할 것 같습니다.