2981번 검문(수학, 유클리드 호제법, 약수) - ☆

#문제링크 : https://www.acmicpc.net/problem/2981

<전략>

1. 그냥 생각나는대로 코드를 작성해서 제출했다가는 시간초과가 난다. 처음 생각한 방법은 주어진 수를 정렬한 후, 두번째로 작은 수 미만 범위에서 모든 수를 나누어보면서 나머지가 같다면 해당 수를 출력하는 방법으로 했다. 중복되는 숫자가 없으므로 두번째로 작은 수 이상부터 나누어 봤자, 동일한 나머지 값을 가지는 M이 생길 수가 없기 때문이다.
(예시 : 3, 6, 14 -> 6이상의 수로 나누어서 나머지를 구하면 6일땐, 두번째로 작은 수가 무조건 나머지가 0이 되고, 첫번째 수와 두번째 수는 무조건 다른 수 이므로 같은 나머지값을 가지지 못한다. 이후, 7이상 부터는 첫번째, 두번째로 작은 수는 무조건, 3, 6이 나머지가 되기때문에 같은 나머지값을 가질 수가 없다.)
->> 시간초과가 발생하는 경우 ->> 주어진 수가 2, 1000000000 인 경우, 10억번의 나머지 연산을 수행해야 한다.

2. 주어진 수를 정렬하고 그 숫자 각각을 n1, n2 , n3... 라 할 때,

ⓐ n1 % M = n2 % M = n3 % M = ... 인 M을 찾는 문제다.

여기서 n1 % M = n1 - (n1 / M) * M이라 할 수 있고, 마찬가지 n2 % M = n2 - (n2 / M) * M라 할 수 있다. 두 식의 값이 같으므로(ⓐ에 의해) 다음과 같은 식을 만들 수 있다.

ⓑ n1 - (n1 / M) * M = n2 - (n2 / M) * M

위 식에서 우변의 n2를 좌변으로 좌변의 n1을 제외한 식을 우변으로 보내면,

ⓒ n1 - n2 = M * (n1 / M - n2 / M)

와 같은 식이 나온다. 위 식을 유심히 보면, n1과 n2의 차이 값은 M을 약수로 가지고 있고, 마찬가지 n2-n3, n3-n4, n4-n5 ... 모든 식에서 M이 해당 차이값의 약수로 포함된다. (참고로 위 식은 양옆에 - 부호를 붙여도 동일한 식이고, 오름차순으로 정리한 상태이므로 n2-n1로 해석하는게 더 바람직 하다.)

즉, 정렬된 각각의 수에 대해 인접한 수와의 차이값은 최대 공약수를 가진다. 이 최대 공약수가 M이 되고, M의 약수 또한, 동일한 나머지 값을 부여하므로, 답은 M과 M의 약수이다. (1은 제외)

3. 여기서 의문이 하나 들 수 있다. 그럼, 왜 1번째와 2번째, 2번째와 3번째, 3번째와 4번째.... 이런 인접한 수의 차이만 가지고 최대공약수를 구해도 답이 되는 것일까...?
그에 대한 답은, 현재 저 수들은 오름차순으로 정렬이 되어 있는 상태다. 만약, 1번째와 3번째 수의 차이를 구해 그 수 또한, 최대공약수를 구하는데 사용한다면, 낭비가 된다. 예를 들어 보자.

<인접한 수의 차이를 이용해 최대공약수 구하기>
n2 - n1 = G * a (G : n2-n1과 n3-n2의 최대공약수)
n3 - n2 = G * b 라 하면, (우리는 이미 이 둘을 통해 최대공약수 G를 구할 수 있다.)

그 상태에서, n3와 n1의 차이를 이용해서 또 추가적인 최대공약수를 구해준다고 생각하면,

<n3 - n1과 n2 - n1을 이용해 최대공약수 구하기>
n3 - n1 = G * a + G * b = G * (a + b) 이고,

n2 - n1 = G * a 였으므로, n2 - n1 과 n3 - n1 의 최대공약수는 G로 결국, 같게 된다. 즉, 이미 구한 최대공약수를 한번 더 구한 셈이다. 따라서, 인접한 수들의 차이만 가지고 최대공약수를 구하면 된다.

 

※주의사항

1. 100여개의 수의 최대공약수를 구한다하면, (((1번, 2번)의 최대공약수, 3번)의 최대공약수, 4번)... -> 이런식으로 구함

2. M의 약수를 구하는 과정에서 제곱근보다 작거나 같은 약수, 제곱근보다 큰 약수를 모두 구해주어야 한다는 점

3. M의 약수의 갯수가 최대 어느정도까지 나올 수 있는지 어림잡아봐야 함. 10억 이하의 수들 중 약수의 갯수가 가장 많은 경우 = "소인수분해 했을때, 가장 많은 '소수'를 보유하고 있는 수" 이므로 어림잡아 소수 9개 ~ 10개로 구성된 수 사이에 있으므로, 약수 갯수를 구하는 공식에 따라 2^10 =1024 보다 큰 10000으로 넉넉히 M의 약수를 담을 배열을 정해주었다.

Code