백준 2981 검문 python

문제링크: https://www.acmicpc.net/problem/2981
문제 관찰: n개의 숫자가 주어짐. n개의 숫자를 m으로 나누었을 때 나머지가 모두 같게 되는 m찾기. 단 m은 1 보다 커야함.
문제 분석:
완전탐색 접근
n개의 숫자 중 가장 작은 값을 찾고, n개의 수를 2~ 가장작은값으로 나누어서 나머지가 같은 경우를 찾는 다. -> 가장 작은 값이 10억인 경우 TLE
나머지로 정리 해본다.
A % M = A - (A//m)m
B % M = B - (B//m)m
C % M = C - (C//m)*m

여기서 부턴 https://pangsblog.tistory.com/62 를 참고 했다. 
대단한 사람들이 많다.

A - B = M(A//M - B//M)
나머지가 모두 같으면 공통된 M을 가짐. 즉, M은 공약수 

문제는 M 모두 찾기
그러므로 최대 공약수의 약수들을 찾으면 된다.

코드

# 최대 공약수를 찾기
def GCD(a, b):
    while a % b != 0:
        x = a % b
        a = b
        b = x
    return b

# 약수 찾기
def find_divisor(x):
    for i in range(1, int(x**(0.5))+1):
        if i * i > x:
            return
        if x % i == 0:
            divisor.append(i)
            if i * i != x:
                divisor.append(x//i)


n = int(input())
# arr[2] - arr[1] 를 양수로 만들기 위해 정렬해줌
arr = sorted(list(int(input()) for _ in range(n)))
divisor = []
# 최대 공약수 저장
gcd = arr[1] - arr[0]
# 배열들의 차와 이전 최대공약수의 최대공약수를 구해줌 
for i in range(n-1):
    gcd = GCD(gcd, arr[i+1]-arr[i])
find_divisor(gcd)
divisor.sort()
print(*divisor[1:])