검문

❓문제

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

❗문제 정리

유클리드 호제법 gcd를 이용한다.
나머지가 같은 수들의 몫== 수들의 차이의 최대공약수의 약수를 구하는 것이다.
a,b,c의 나머지가 같은 몫==(a-b), (b-c)의 최대공약수의 약수를 구하는 것이다.

• python은 시간 초과로 pypy로 출력

📑코드

import sys
input=sys.stdin.readline #시간초과 방지

def gcd(a, b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)
#---------------------------------------------------------
n=int(input())#수의 개수
nums=[]
for _ in range(n):
    nums.append(int(input()))
nums.sort(reverse=True)#내림차순
#---------------------------------------------------------
#나머지가 같은 a,b,c,d의 몫을 구하는 것은 a-b, b-c,c-d의 최대공약수의 약수이다.
#최대공약수 구하기------------------------------------------
if n==2:#2개의 수가 주어질때는 두수의 차를 구해서 m으로 두기
    m=nums[0]-nums[1]

else:
    m=gcd(nums[0]-nums[1],nums[1]-nums[2])#첫 2개의 값의 최대공약수구하고
    if n>=3:
        for i in range(3,n):#받은숫자만큼
            m=gcd(m,nums[i-1]-nums[i])#구한 값과 이후값이 최대공약수구하기

#최대공약수 약수 구하기-------------------------------------
for i in range(1,m+1):#최대공약수로 무언가를 나눠서 0이 되면 그것은 최대공약수의 약수
    if m%i==0 and i!=1:#1보다 커야한다다는 문제 지시
        print(i,end=' ')

📝코드 설명

def gcd(a, b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

최대공약수를 구하기 위한 gcd 함수 정의

n=int(input())#수의 개수
nums=[]
for _ in range(n):
    nums.append(int(input()))
nums.sort(reverse=True)#내림차순

수의 개수n과 수를 입력받아서 내림차순으로 정렬한다.(수의 차이를 양수로 계산하기 위함)

최대공약수구하기

if n==2:#2개의 수가 주어질때는 두수의 차를 구해서 m으로 두기
    m=nums[0]-nums[1]

else:
    m=gcd(nums[0]-nums[1],nums[1]-nums[2])#첫 2개의 값의 최대공약수구하고
    if n>=3:
        for i in range(3,n):#받은숫자만큼
            m=gcd(m,nums[i-1]-nums[i])#구한 값과 이후값이 최대공약수구하기

n==2인 경우, 최대공약수가 나오지 않는 수가 있을 수 있기에 두 수의 차를 구한다.
n==3이상인 경우, 수들의 차이를 계산하여 앞의 최대공약수를 구한다.

#최대공약수 약수 구하기-------------------------------------
for i in range(1,m+1):#최대공약수로 무언가를 나눠서 0이 되면 그것은 최대공약수의 약수
    if m%i==0 and i!=1:#1보다 커야한다다는 문제 지시
        print(i,end=' ')

최대공약수의 약수를 구한다.

🎖제출 결과

💡insight