[Python] 백준 #1684 같은 나머지(정수론)

이번 문제는 주어진 숫자들에 대해서 나머지가 같은 수가 되는 나눔수 중 최대의 정수를 찾는 것입니다.

 

 

나머지가 같다는 것은, 숫자들의 차이에 대한 최대공약수를 구하는 것과 같습니다.

 

\[ Find~ maximum~ such~ D~ that~ \forall i ~ a_i ~mod ~D = k \Longleftrightarrow gcd( a_i - min(a) ) \]

 

음수를 피하기 위해서 주어진 수 중에 가장 작은 수를 찾습니다.

그리고 나머지 수 중에 가장 작은 수와 같은 경우를 제외하고, 그 차이를 기록합니다.

마지막으로 그 차이들의 수열의 최대 공약수를 구합니다.

 

다음은 제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

"""
    baekjoon #1684
        - by Aubrey Choi
        - created at 2022-09-29
"""
import math
n = int(input())
v = list(map(int, input().split()))
m = min(v)
t = [v[k]-m for k in range(n) if v[k]!=m]
g = t[0]
for k in range(1, len(t)): g = math.gcd(g, t[k])
print(g)