공부/알고리즘
[단계별로 풀어보기][Python 3] 정수론 및 조합론 - 검문(2981)
도리암
2022. 5. 3. 17:17
2981번: 검문
트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간
www.acmicpc.net
위 문제를 풀기 위해서는 수학적인 계산이 먼저 필요하다.
수식 도출
각 숫자를 m으로 나눴을 때 나머지가 동일해야 하므로 다음의 식을 세울 수 있다.
위의 식에서 r이 동일하게 나오므로, 각 항목을 빼주면 m을 최대공약수로 가지는 수가 도출된다.
풀이
def gcd(a, b):
while b != 0:
r = a % b
a = b
b = r
return a
n = int(input())
num = sorted([int(input()) for _ in range(n)])
re_num = [num[i+1]-num[i] for i in range(n-1)]
g = re_num[0]
for i in range(1, len(re_num)):
g = gcd(g, re_num[i])
res = set()
for i in range(2, int(g**0.5)+1):
if g%i == 0:
res.add(i)
res.add(g//i)
res.add(g)
print(*sorted(list(res)))각 수를 num에 저장하고, 뺄셈을 했을 때 양수가 나올 수 있도록 정렬해준다.
re_num에 num의 각 요소의 차이를 저장한뒤 모든 수의 최대공약수를 구해준다.
최대공약수를 구했으면 그 최대공약수의 약수를 구한다.
이 때, 수의 범위가 1,000,000,000으로 매우 크므로 제곱근까지만 시도하여 수행 시간을 줄인다.
print(*list)를 하면 리스트의 전체 요소를 대괄호 없이 출력해준다.
