신비로운 수

2981-검문과 유사한 문제이다.

주어진 수들의 차이의 최대 공약수를 구하면 되는데, 왜 이 수로 각각의 숫자들을 나누면 나머지가 모두 나머지가 같아지는지 알아보자.

서로 다른 두 수 a와 b가 있고, 이 수들을 m으로 나눴을 때 나머지가 x로 동일하다.

a % m = x … 1)

b % m = x … 2)

1)에서 2)를 빼면 아래와 같은 식이 된다.

(a - b) % m = 0

이 식으로 부터 두 수의 차가 m의 배수일 때, 두 수를 m으로 각각 나누면 나머지가 같음을 알 수 있다.

따라서, 숫자들이 주어졌을 때, 각 숫자들의 차를 구하고 이 ‘차’들의 최대공약수를 구하면 가장 큰 신비로운 수를 알 수 있게 된다. (‘차’들이 모두 0인 경우 숫자들이 모두 같다는 의미임으로, INFINITY를 출력한다.)

유클리드 호제법을 이용하여 최대공약수를 구하는 방법은 최소공배수 포스팅에서설명해 두었다.

def GCD(x, y):
    while y != 0:
        x, y = y, x % y
    return x


수 들을 입력받고, 이 수들의 차를 구했다. 중복되는 차들을 걸러주기 위해 집합 자료구조를 사용했다.

x = diff[0]
for i in range(1, len(diff)):
    x = GCD(x, diff[i])

diff에 차들을 저장해놓은 후 위의 코드를 이용해서 이 수들의 최대공약수를 구할 수 있었다. 위의 for문을 돌고 나온 x가 최종적으로 가장 큰 신비로운 수가 된다.


CODE

import sys
read = sys.stdin.readline

#유클리드 호제법을 사용해 최대공약수를 구한다.
def GCD(x, y):
    while y != 0:
        x, y = y, x % y
    return x


for _ in range(int(read())):
    n = int(read())
    num = list(map(int, read().split()))
    #밑에서 두 수의 차를 diff에 추가할 때, 음수가 나오지 않게 하기 위해서
    #정렬을 먼저 해주었다. 정렬을 하지 않고, 두 수의 차의 절대값을 diff에 추가해도 무방하다.
    num.sort()

    diff = set()
    for i in range(1, n):
        diff.add(num[i]-num[i-1])
    diff = list(diff)

    if diff == [0]:
        print('INFINITY')
        continue

    x = diff[0]
    for i in range(1, len(diff)):
        tmp = GCD(x, diff[i])
        x = tmp
    print(x)


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]