[백준] 2981번 (python 파이썬)

https://www.acmicpc.net/problem/2981

 

수학적 이론이 필요한 문제이다.

M 을 찾아야한다.

 

A = M * a + R

B = M * b + R

C = M * c + R

 

여기서 R을 제거하면

A - B = M ( a - b )

B - C = M ( b - c )

이런 식이 나온다.

즉,

 M은 A-B, B-C의 공약수이다 즉 최대공약수를 구하면 된다.

최대 공약수를 구하고 해당 수의 1을 제외한 약수를 출력하면된다.

 

이때 최대 공약수를 구하고 약수를 구할때 반복문을 최대공약수 까지 돌려버리면  숫자 범위가 1,000,000,000까지기 때문에 엄청난 시간이 걸린다.

 

그래서 공약수를 구할때

18 % 2 = 0 ( 2 = 약수)

18 // 2 = 9 ( 9 = 약수)

이 2개를 한번에 구한다 이러면 반복횟수를 최대공약수의 제곱근 까지 줄일수 있다.

마지막에 자기 자신도 추가한다.

 

from math import gcd
from math import sqrt

n = int(input())
ns = list(int(input()) for _ in range(n))
ns.sort()
interval = list()
ans = list()

for i in range(1, n):
    interval.append(ns[i] - ns[i - 1])

prev = interval[0]
for i in range(1, len(interval)):
    prev = gcd(prev, interval[i])

for i in range(2, int(sqrt(prev)) + 1): #제곱근까지만 탐색
    if prev % i == 0:
        ans.append(i)
        ans.append(prev//i)
ans.append(prev)
ans = list(set(ans)) #중복이 있을수 있으니 제거
ans.sort()
print(*ans)