[연습문제][python]최대공약수

 

주어진 N개의 수에서 차이를 구하고, 그 차이들의 최대 공약수를 구하기

M의 후보군 : 차이의 최대 공약수의 약수

1. 차이들의 최대 공약수(GCD)를 구하는 이유

N개의 수에서 나머지가 모두 동일하게 되는 M을 찾으려면 다음과 같음.

예를 들어, 두 수가 있다고 가정

• A = 25
• B = 10

이 두 수를 M으로 나눴을 때 나머지가 같다면, 다음과 같은 조건이 성립해야 함. 

• 25 % M == 10 % M

이 식을 전개하면, 두 수의 차이가 M으로 나누어 떨어지는 수여야 함

• (25 - 10) % M == 0, 즉 15 % M == 0

이 조건을 N개의 모든 수들에 대해 적용하기 위해, N개의 수들 간의 차이를 구하고, 그 차이들의 **최대 공약수(GCD)**를 구함. 

2. 최대 공약수(GCD) 구하기

최대 공약수는 두 수를 나눌 수 있는 가장 큰 공통 약수이다. 예를 들어, 두 수 15와 10의 최대 공약수는 5입니다. 세 수의 최대 공약수를 구할 때는, 먼저 두 수의 GCD를 구한 후, 그 결과를 세 번째 수와 비교하여 다시 GCD를 구하는 것 반복 -> 이를 반복하면 N개의 수에 대해 최대 공약수를 구하는 법 :

최대 공약수는 유클리드 호제법알고리즘 사용. 

• GCD(A, B) = GCD(B, A % B)
• 이 과정을 B가 0이 될 때까지 반복하면, 그때 A가 최대 공약수가 됨

예를 들어, GCD(15, 10)을 구하면:

• 15 % 10 = 5
• GCD(15, 10) = GCD(10, 5) = GCD(5, 0) = 5

이 과정은 시간 복잡도가 매우 효율적!!!!!!!(대략 O(log(min(A, B)))).

3. GCD의 약수 구하기

최종적으로, 구한 GCD의 약수들이 모두 가능한 M의 후보가 된다. 약수란, 어떤 수를 나누어 떨어지게 할 수 있는 수. 예를 들어, GCD가 12라면 그 약수는 1, 2, 3, 4, 6, 12가 됨.

약수를 구하는 방법은, 1부터 GCD의 제곱근까지 반복하며, GCD를 나누어떨어지게 하는 수들을 찾는 방식.

예를 들어 12의 약수를 구할 때:

• 1부터 12의 제곱근(약 3.46)까지 반복하면서 12를 나누어 떨어뜨리는 수를 찾음.
• 1, 2, 3이 12를 나누어떨어뜨릴 수 있고, 각각의 몫인 12, 6, 4도 약수.

이런 방식으로 GCD의 모든 약수를 찾으면, 그 약수들이 곧 모든 가능한 M이 됨

전체 알고리즘 요약

1. 차이 구하기: 주어진 N개의 수들 사이의 차이를 계산
2. 최대 공약수(GCD) 구하기: 구한 차이들 간의 GCD를 구함
3. 약수 구하기: GCD의 모든 약수를 구하여 가능한 M 후보들을 도출

예시

주어진 수가 10, 25, 5라고 가정

1. 차이 구하기:
   • 차이: |25 - 10| = 15, |10 - 5| = 5
   • 차이: 15, 5
2. 최대 공약수 구하기:
   • GCD(15, 5) = 5
3. 약수 구하기:
   • 5의 약수는 1과 5
   • 따라서 가능한 M은 1과 5

 

 

 

 

import math

# 입력 처리
N = int(input())  # 종이에 적은 수의 개수
numbers = [int(input()) for _ in range(N)]  # N개의 수 입력

# 수들을 오름차순 정렬
numbers.sort()

# 차이들의 최대공약수 구하기
gcd_result = abs(numbers[1] - numbers[0])  # 첫 번째 두 수의 차이로 시작
for i in range(2, N):
    gcd_result = math.gcd(gcd_result, abs(numbers[i] - numbers[i - 1]))

# 최대공약수의 약수 구하기
result = []
for i in range(1, int(math.sqrt(gcd_result)) + 1):
    if gcd_result % i == 0:
        result.append(i)
        if i != gcd_result // i:
            result.append(gcd_result // i)

# 약수들을 오름차순으로 정렬
result.sort()

# 결과 출력
print(" ".join(map(str, result)))