백준 골드 (2981번) 파이썬

---

N = input()
list = []
M=[]
check=0
for x in range(int(N)):
  inp=int(input())
  list.append(inp)

for x in range(2,int(min(list))+1):
  for y in range(int(N)):
    ms=list[y]%(x)
    M.append(ms)
    a=M[0]
    b=M[y]
    if(a!=b):
      check=1
      break
      
  if(check!=1):
    print(x)

  M=[]
  check=0

 

(일단은 돌아가는 코든데 쓴게 아까워서 올리는 오답)

 

이건 오답이다. 

사실 이거 돌려봐도 답은 제대로 나온다. 

근데 왜 오답이냐고?

 

만약 이게 정답이였다면 문제가 골드일 리가 없겠지. 

시간초과가 뜬다. 

 

이유는 다음과 같다:

N이 1,000,000,000 보다 작거나 같은 수 이기에 일일히 나머지를 찾는 방식을 쓰면 컴퓨터가 좆된다ㅋㅋㅋㅋㅋㅋ

문제를 제대로 안읽은걸 반성하자. 

시발.

 

---

그래서 쓴 방법은 수학을 사용하는것이다. 

한국수학 수학 상에 나오는 내용을 그대로 사용해서 연립방정식을 풀면 답이 나온다 (이건 내 과외 말버릇)

마침 내 학생중 하나가 수학 상을 하니 이걸 숙제로 내줄까도 생각중임 

 

이렇게 연립방정식을 만들어서 나머지 R을 없애주고 M에 대한 식을 만듧

 

import math
N = int(input())
s = []
M = []
gcd = 0 #greatest commend divisor (최대공약수)
for i in range(N):
    s.append(int(input()))
    if i == 1:
        gcd = abs(s[1] - s[0])
    gcd = math.gcd(abs(s[i] - s[i - 1]), gcd)
gcd_last = int(gcd ** 0.5) #너무 많이 돌리면 시간초과뜸
for i in range(2, gcd_last + 1):
    if gcd % i == 0: #최대공약수가 어떤 수로 나눠졌을때 나머지가 0이 되면 그 어떤 수는 최대공약수의 약수가 된다 (즉 약수찾는 반복문임)
        M.append(i) 
        M.append(gcd // i) #최대공약수를 반갈죽해서 넣어주는거랑 동시에 하면 연산이 줄어듦 (gcd ** 0.5 최대공약수의 루트만큼만 계산하기 때문) 시간초과 방지
M.append(gcd) #당연히 최대공약수도 넣어줘야지
M = list(set(M)) #중복제거
M.sort() #정리함
for i in M:
    print(i, end = ' ')

 

자세한 설명은 생략한다. (위에 이미 다 주석으로 설명되있음)