알고리즘 유형 : 정수론
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/2981
소스 코드(파이썬)
N = int(input())
num = sorted([int(input()) for _ in range(N)])
re_num = []
# B-A, C-B, D-C... 쭉 구해서 새 리스트에 추가
for i in range(1, N):
re_num.append(num[i] - num[i-1])
# 두 수의 최대공약수를 구해주는 함수(유클리드 호제법)
def findGCD(a, b):
num = b
div = a
rest = num % div
while rest != 0:
num = div
div = rest
rest = num % div
return div
# re_num의 모든 수들의 최대공약수를 구하고 그 것의 1을 제외한 모든 약수가 구하는 M이다.
GCD = re_num[0]
for idx in range(1, len(re_num)):
GCD = findGCD(GCD, re_num[idx])
# 왜 수의 제곱근까지만 약수를 구해주고, 각 단계에서 약수를 두개 저장하는 건 또 뭔가 싶을 것이다.
# 예를 들어 36의 약수는 1을 제외하고 1, 2, 3, 4, 6, 9, 12, 18, 36인데, 2 * 18 = 36, 3 * 12, ..., 6 * 6 = 36
# 이와 같이, 제곱근의 경우 그 자신을 제곱하면 원래 수가 되고, 그 이전의 모든 수는 제곱 수보다 큰 어떤 약수와 매칭돼서
# 원래 수를 이루게 된다. 그래서, 제곱근 이전의 모든 약수의 개수 * 2와, 제곱근 약수 하나를 더한 것이 전체 약수의 개수가 된다.
# 그런데 지금 경우는 1은 제외하므로, 2부터 제곱근까지 for를 돌고, 제곱근일 때는 제곱근이 두 개 저장되므로 중복을 피하기
# 위해 set에 저장한다. 그리고 1일 때를 제외했으므로, 마지막 자기 자신인 GCD가 포함되지 않았으므로 따로 추가해준다.
result = set()
for i in range(2, int(GCD**0.5) + 1):
if GCD % i == 0:
result.add(i)
result.add(GCD // i)
result.add(GCD)
print(*sorted(list(result)))풀이 요약
-
수학적 지식이 필요하다.
A = M * a + R
B = M * b + R
C = M * c + R
이렇게 둬보자.(문제 조건에 부합하는 식, M으로 각 수를 나눴을 때 나머지가 모두 같다)
B - A = M(b-a)
C- B = M(c-b)
이런 원리로, A~Z까지 입력받은 모든 수에 대해(오름차순), M은 B - A, C -B, ..., Z - Y의 공약수들이다.
즉, 이웃한 것끼리 뺀 수들의 최대공약수의, 1을 제외한 모든 약수가 M이 될 수 있는 것이다.
-
입력받은 수들을 오름차순으로 정렬하고, for를 돌면서 B - A, C - B, ..., Z - Y들로만 이루어진 새 리스트 re_num을 만든다.
-
re_num의 모든 수들의 최대공약수 GCD를 구하면 된다.
GCD에 re_num[0]을 저장하고, re_num을 쭉 돌면서, GCD에 들어있던 값과 re_num의 현재 순회 중인 수와 또 최대공약수 연산을 해서 계속 GCD를 업데이트해주면 된다.
-
이제 GCD의 1을 제외한 모든 약수를 구하면 그 것이 구하고자 하는 모든 M이다.
-
그런데 입력받았을 때 수의 범위가 10억까지 이므로, 지금 구한 GCD도 아주 큰 수일 수 있는데, 약수를 구할 때 1부터 GCD까지 다 돌아버리면, 몇 억번을 연산하게 될 수도 있으므로, 대충 1억 번에 1초이므로 시간 초과가 되버릴 가능성이 있다. 다행히 for를 돌 범위를 줄일 수 있다.
-
예를 들어, 36의 경우 약수는 1 2 3 4 6 9 12 18 36 이다.
잘 보면, 제곱근인 6 이전의 모든 수에 대해, 1 36 = 36, 2 18 = 36, 이런 식으로 제곱근보다 큰 어떤 약수와 매칭되어 원래의 수를 이룰 수 있다. 즉, 제곱근 이전의 약수의 개수의 곱하기 2만큼과, 제곱근이 자연수인 경우 그 수 한번만 카운팅해주면 된다. 6 * 6 = 36으로 6을 두 번 저장해버리면 안되기 때문. 그래서 set에 담는 것이다.
-
이 때, for를 돌 때 1을 제외하고 구했으므로, 1와 매칭되는 36이 포함되어 있지 않다. 그래서 마지막에 GCD 값 자체를 한 번 따로 추가해준다.
-
이 후 set을 list로 형변환 후 정렬 및 출력해주면 끝!
배운 점, 어려웠던 점
-
문제의 조건을 수식으로 직접 표현해서 M이 의미하는 바를 파악하는 데 미흡했다. 이 아이디어 외에, 첫 번째 수를 그 이후의 모든 수에 빼준뒤에, 그 후 모든 수들의 GCD를 구하는 아이디어는 떠올리긴 했는데, 위에 작성한 저 방법이 수학적인 식으로 깔끔하게 근거가 나오고, 수의 크기 자체도 줄고 더 좋은 것 같다.
-
GCD가 n억에 가까운 수일 경우를 간과하고, 시간 초과를 고려하지 못했다. 다른 사람 풀이 참고를 통해, 약수를 오름차순으로 나열했을 때, 제곱근 이전의 약수들은 모두 제곱근 이후의 약수와 매칭되고, 따라서 약수의 개수는 (제곱근 이전의 모든 약수 * 2) + 제곱근(자연수인 경우에만 카운팅) 임을 알게 되었다.
