109. 2981(검문)

import sys
input = sys.stdin.readline

T = int(input())
num = sorted([int(input()) for _ in range(T)])
result = set()


def GCD(x, y):
    while(y != 0):
        r = x % y
        x = y
        y = r
    return x


numGCD = num[1]-num[0]
for i in range(2, T):
    numGCD = GCD(numGCD, abs(num[i]-num[i-1]))


for j in range(2, int(numGCD**0.5)+1):
    if(numGCD % j == 0):
        result.add(j)
        result.add(numGCD//j)
result.add(numGCD)

print(*sorted(list(result)))

문제요약

수가 주어졌을 때 M으로 나눌 때 나머지가 동일한 경우의 M을 구하라. (상근아... 검문이나 제대로 받아;;) 

설명

최대 1,000,000,000이라는 어마어마한 숫자로 인해 시간초과가 발생할 확률이 높은 문제이다.

 

수의 형태는 A = B * C + R 이다.

예를들어 A가 19이면 19 = 5 * 3 + 4 이며 위의 문제 첫번째 예시인  6 , 34 , 38에 적용하면,

다음과 같다.

 

M으로 나누었을 때 두 값의 나머지는 동일하다는 조건으로 인해,

다음과 같은 식이 완성된다.

 

이때, (6-34) / M 의 M과 (34-38) / M 의 M의 M이 같다.

때문에 (6-34) 와 (34-38)의 공약수를 구하면된다. 즉, 28과 4의  최대공약수를 찾고 그 최대공약수의 약수를 구하면 된다.

 

이를 빠르게 두번째 입력에 적용해 보면 다음과 같다.

 

입력 => 5 17 23 14 83

 

num = sorted([int(input()) for _ in range(T)])

정렬을 통해 다음값 - 현재값을 하여 음수가 발생하지 않도록 할 것이다.

def GCD(x, y):
    while(y != 0):
        r = x % y
        x = y
        y = r
    return x

유클리드 호제법을 사용하여 최대공약수를 구한다.

numGCD = num[1]-num[0]
for i in range(2, T):
    numGCD = GCD(numGCD, abs(num[i]-num[i-1]))

먼저 numGCD를 만들고 (만약 TestCase가 2개이면, 그게 바로 최대공약수가 된다.) , 최대공약수를 구해간다.

예들들어 

다음과 같이 진행되는 것이다.

for j in range(2, int(numGCD**0.5)+1):
    if(numGCD % j == 0):
        result.add(j)
        result.add(numGCD//j)
result.add(numGCD)

print(*sorted(list(result)))

수가 커지면 끝까지 반복문을 돌리기에는 시간이 많이 걸린다.

때문에 제곱근 이후부터는 나눠도 의미없다는 것을 이용하여 반복 횟수를 줄인다.

 

예를들어 10의 제곱근은 3.16이다.

4 이후 부터는 이미 앞에서 구한 값으로 약수를 구할 수 있고, 제곱근 약수가 없다면 이후에도 약수가 없다.

 

위 로직을 그림으로 설명하면 다음과 같다.

만약 나누는 수가 중복이 발생할 수도 있기 때문에 집합(set)에 값을 집어넣고 리스트로 바꾼 뒤 정렬을 통해 출력을 한 것 이다.