[백준 파이썬 2981번]검문★약수구하기★애스터리스크(Asterlisk)★

import sys
import math

N = int(sys.stdin.readline())
maxs=0
A = []
for i in range(N):
    a = int(sys.stdin.readline())
    A.append(a)
A= sorted(A)
res = []
for i in range(1,len(A)):
    if i==1:
        maxs = A[i]-A[i-1]
    maxs = math.gcd(A[i]-A[i-1] , maxs)

for i in range(1,int(maxs**0.5)+1):
    if maxs%i == 0:

        if ( (i**2) != maxs) :
            res.append(maxs // i)
        if i!=1:
            res.append(i)
print(*sorted(list(set(res))))

1. 수학적 지식 활용

 

ex) 6 34 38 

maxs = 34-6

1) 34-6 = [28 gcd 28] ==>28

2) 38-34 = [4 gcd 28] ==> 4

 

1을 제외한 약수구하면 나머지값이 모두 동일하다.

 

 

2. 약수구하기 시간복잡도 생각에 따른 식 세우기

 

1) for i in range(1, int(8**0.5)+1) = for i in range(1, 3)

2) maxs = 8 ==> 8%(1과2) ==0

3) 1**2 = 1 != maxs(8) ==> 8//1 = 8 

4) 2**2 = 4 != maxs(8)  != 1 ==> 8//2 =4 , 2 추가 

 

 

3. 리스트 출력하는 애스터리스크(Asterlisk) ==> *

 

a = [1,2,3,4]

print(*a) ==> 1 2 3 4