https://www.acmicpc.net/problem/2981
실패이유 : 시간초과
import math
def find_divisors(n): # 약수를 구하는 함수
divisors = []
for i in range(1, int(n ** (1 / 2)) + 1): # 최적화를 위해 제곱근까지만 for 문
if n % i == 0:
divisors.append(i)
divisors.append(n // i)
divisors = sorted(list(set(divisors)))
divisors.remove(1)
return divisors
N = int(input())
numbers = sorted([int(input()) for _ in range(N)])
if N == 2: # 입력 숫자가 2개면 차의 약수들을 바로 구한다.
ans = find_divisors(abs(numbers[0] - numbers[1]))
else: # 입력 숫자가 여러개면 최대공약수를 구한 뒤 약수들을 구한다.
gcd = abs(numbers[0] - numbers[1])
for i in range(1, N - 1):
gcd = math.gcd(abs(numbers[i] - numbers[i + 1]), gcd)
ans = find_divisors(gcd)
for i in ans:
print(i, end=" ")
N[0] = M * a + R
N[1] = M * b + R
N[2] = M * c + R
- N[i] : 입력받은 정수들 (오름차순 정렬)
- M : 구하려는 값, 약수들
- R : 나머지
R을 제거하기 위해
N[0] - N[1] = M (a-b)
N[1] - N[2] = M (b-c)
- 따라서 이웃한 N[0] - N[1] 과 N[1] - N[2] 의 최대공약수인 가장 큰 M 을 구한 뒤
- 최대 공약수 M 의 1을 제외한 약수들을 구해서 출력하면 된다.
- find_divisors( ) 함수 사용
- for문을 제곱근까지만 돌려서 시간 최적화
