백준 22.03.17. 2981번 - 검문

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

유클리드 호제법은 최대공약수를 구할 때 사용되는 방법이며 큰 수(A)를 작은 수(B)로 나누어 그 나머지를 이용하여 최대공약수를 구하는 방법입니다

---

 

• 이 문제를 풀기위해 방정식으로 정리를 해보았습니다
• A, B 두개의 수가 같은 나머지 값을 갖도록 하는 수를 구하려면 방정식은 다음과 같습니다
• d = 최대공약수, r = 나머지입니다
• A = a * d + r, B = b * d + r
• 이것을 계산해보면 (A - B) = (a - b) * d 입니다
• 이것으로 우리는 d가 (A-B)의 약수라는 것을 알 수 있습니다

import math

N = int(input())

nums = []
divs = set([])
gcd = 0

for i in range(N):
    nums.append(int(input()))
    if i == 1:
        gcd = abs(nums[1] - nums[0])
    gcd = math.gcd(abs(nums[i] - nums[i-1]), gcd)

rgcd = int(math.sqrt(gcd))

for i in range(2, rgcd+1):
    if gcd % i == 0:
        divs.add(i)
        divs.add(gcd//i)

divs.add(gcd)
divs = sorted(list(divs))

for i in divs:
    print(i, end=" ")

• 우선 받은 숫자들을 저장할 nums 리스트와 약수들을 저장할 set형식의 divs, 그리고 최대공약수를 저장할 gcd를 생성합니다
• 반복문에 따라 nums에 숫자들을 저장하며 만약 두개의 숫자가 받아졌을 때, gcd의 초깃값 설정을 위하여 조건문으로 gcd를 할당합니다
• math모듈을 임포트하여 gcd메서드를 사용합니다
  • gcd메서드는 최대공약수(greatest common divisor)를 구하는 메서드입니다
• 이후 위에서 서술했듯 (nums[i] - nums[i-1])과 (nums[i-1] - nums[i-2])최대공약수였던 gcd의 최대공약수를 구해줍니다
  • 여기서 구하는 약수들은 나머지 값을 동일하게 갖게 하는 약수입니다
• 최대공약수는 갱신되며 gcd에 저장되고 이것의 제곱근인 rgcd를 생성합니다
  • 제곱근처리해주는 이유는 N이라는 수가 주어졌을때, N의 약수들을 오름차순으로 정리한 후, 절반을 나누었을 때, 가장 큰 값은 가장 큰 약수의 제곱근보다 작거나 갖기 때문입니다
    • ex) 32의 약수는 [1, 2, 4, 8, 16, 32]이며 절반을 나누어 가장 큰 값은 32의 제곱근보다 작거나 같습니다
• 그리고 M은 1보다 커야하므로 반복문을 2부터 rgcd까지 실행합니다
• 이 과정에서 나온 i가 gcd를 나눴을 때 나머지가 없이 딱 떨어진다면 i 역시 약수입니다
  • A = a * b 일 때, a와 b는 모두 A의 약수입니다 
• 따라서 i와 gcd//i를 모두 divs에 저장해줍니다
• 위 작업이 끝났다면 divs를 list형태로 변환하여 정렬해줍니다
• 이것을 양식에 맞게 출력해주면 됩니다