백준 2981번 (math 모듈)

처음에는 간단하게 모든 경우에 따라 다 나누어서 구해보려고 했다.

import sys

def input():
    return sys.stdin.readline().rstrip()

N = int(input())

L = []

for i in range(N):
    L.append(int(input()))

M = 2
Max = max(L)
while M < Max:
    X = L[0]%M
    temp = False
    for i in L:
        if i%M != X:
            temp = True
            break
    if temp == False:
        print(M, end=' ')
    M += 1

 

하지만 당연하다 싶이 시간 초과 판정을 받았다.

 

아무리 생각해도 모르겠다 싶어 수학적 원리를 검색해보았다.

A = M * a + R

B = M * b + R

C = M * c + R

 

여기서 R을 제거하면

A - B = M ( a - b )

B - C = M ( b - c )

이런 식이 나온다.

M은 A-B와 B-C의 공약수들이다. 즉 최대공약수를 구하면 다 알 수 있다.

 

** gcd는 최대공약수를 구하는 함수, sqrt는 제곱근을 구해주는 함수이다.