[Python]수학3 백준 2981

   문제

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

가장 먼저 든 생각은 N개의 수중 가장 작은수에서 2~n-1까지 나눠서 나머지가 나오는

경우 다음으로 넘어가 그수로 나눠서 나머지를 확인해 같은지 확인하는 방식이다. 

매우 오래걸릴것으로 예상된다.

M의 후보군을 조금 줄여보자

위문제를 살펴보면 주어진수를 A,B로 봤을때

A=a*M+r

B=b*M+r

이라고 표현할수 있다.

 큰수에서 작은수를 빼주면 나머지가 제거되는것을 알수있고

A-B=(a-b)*M 두 수를 빼서 나오는 숫자의 약수에 M이 포함되있는것을 확인할 수 있다.

그렇다면 문제를 해결하기위해 주어진수중 큰수에서 작은수를 빼고 M의 후보군을

 구한후 각 수에 M후보군을 하나씩 나눠 나머지가 같은지 보면 될것이다.

약수를 구하는과정에서 시간초과가 떠서 다른방법을 사용했다.

import math
 
 
N=int(input())
num_list=[]
#A-B를 통해 m구하기
while N>0:
    N-=1
    num_list.append(int(input()))
 
if num_list[0]<num_list[1]:
    m=num_list[1]-num_list[0]
else:
    m=num_list[0]-num_list[1]
    
#약수구하기
m_candidate=[m]
for i in range(2,int(math.sqrt(m))+1):
    if m%i==0:
        m_candidate.append(i)
        m_candidate.append(m//i)
 
#M구하기
M=[]
for i in range(len(m_candidate)):
    r=num_list[0]%m_candidate[i]#나머지 구하기
    for j in range(1,len(num_list)):
        #나머지 같은지 확인
        if r!=num_list[j]%m_candidate[i]:#나머지가 다르면 패스
            break
        if j==len(num_list)-1:#모든 나머지가 같으면 m추가
            M.append(m_candidate[i])
 
M.sort()
 
 
for k in M:#모든 M 출력
    print(k,end=' ')