백준 14476번 최대공약수 하나 빼기

<백준 14476번 최대공약수 하나 빼기>

사용한 알고리즘: 세그먼트 트리


세그먼트 트리로 N개의 수의 gcd를 쌓아올렸습니다. 따라서 arr[1] 은 전체 수들의 공통 gcd 를 나타내게 됩니다.

이후 N개의 수들을 하나씩 0으로 바꿔가며 전체 gcd (arr[1]) 의 변화를 체크했습니다.
이 과정에서 전체 gcd가 증가하는 경우 그 값과, 바꿔준 노드의 원래 값을 저장했습니다.
이때 업데이트 방식은 해당 노드를 0으로 바꾸는 것으로 했으며, 어떤 수 A 와 0 의 gcd(A,0) = A 임을 이용했습니다.

제한시간에 거의 딱 맞춰서 돌아간 것 같습니다. 사실 더 쉽거나 빠른 풀이가 있을 것 같습니다....