백준 2981번 - 검문

어떤 수로 나누었을 때 모두 나머지가 같게 되는 수를 찾는 문제이다.  A를 M으로 나누었을 때 나머지를 R이라고 하면,

A = M * a + R

B = M * b + R

C = M * c + R

위의 식이 성립한다. R을 없애기 위해 각 식을 빼보면, 

A - B = M(a-b)

B - C = M(b-c)

위 처럼 M은 각 수의 차의 공약수이다.

 

각 수들의 차를 먼저 구하고 그 수들의 최대공약수를 구한 뒤에 1을 제외한 약수들을 출력해주면 된다.

##함수 선언 부분##
from math import gcd

##변수 선언 부분##
A = []
B = []
min = 0
min_i = 0
tmp = 0
divisor = []
##메인 함수 부분##
if __name__ == "__main__":
    N = int(input())
    for i in range(N):
        A.append(int(input()))

    A.sort() #차를 구하기 위해 정렬
    for i in range(1,N):
        B.append(A[i]-A[i-1]) #차를 구해줌

    tmp = B[0]
    for i in range(1,len(B)):
        tmp = gcd(tmp,B[i]) #처음부터 마지막까지 gcd를 갱신하며 반복문 순회
    for i in range(2, int(tmp**0.5)+1): #약수를 구할 때 자기자신까지 반복문을 돌리면 시간초과
        if tmp % i == 0:
            divisor.append(i)
            divisor.append(tmp//i)

    divisor.append(tmp) #자기자신도 append
    divisor = list(set(divisor)) #중복 값을 제거하기 위해 set로 변환했다가 다시 list로 변환
    divisor.sort() #오름차순 정렬
    print(*divisor)

입력 값이 1,000,000,000까지라 시간초과를 유의해서 풀었어야했다.