163. GCD Segment Tree

연속된 원소들의 최대공약수를 빠르게 구하는 GCD 세그먼트 트리(GCD Segment Tree)에 대해 알아본다.

---

이 세그먼트 트리의 구성 방법은 간단하다. 리프 노드에 수열의 값들을 저장하고 부모 노드에 양 자식 노드에 저장된 값의 최대공약수를 저장하는 것이다. 다음과 같은 수열이 있다고 할 때,

$$a = [48, 32, 24, 36, 18, 30, 20]$$

이 수열을 GCD 세그먼트 트리로 표현하면 다음과 같다.

리프 노드가 빌 경우 $0$으로 채우면 된다. $x \ne 0$일 때 $\gcd(x, 0) = |x|$이므로 $20$과 $0$의 부모 노드에는 $20$이 저장된다. 또한 $\gcd(0, 0)$은 정의되지 않지만 일반적으로 그러는 것처럼 $0$으로 간주하면 된다.

 

이제 이 세그먼트 트리를 이용해서 두 가지의 쿼리를 처리할 수 있다.

$1\ x\ y$: $x$번째 수를 $y$로 바꾼다.

$2\ x\ y$: $x$번째 수부터 $y$번째 수까지의 최대공약수를 출력한다.

 

$1$번 쿼리와 $2$번 쿼리 모두 일반적인 세그먼트 트리와 같은 방식으로 처리하면 되는데, 합, 최댓값, 최솟값 등의 연산 대신 GCD 연산을 사용한다는 점만 다르다.

 

[연습문제]

 

CF 1548B. Integers Have Friends (1800)

$\gcd(x, y) = \gcd(x, y - x)$라는 성질을 이용해 차이 배열을 만들고, 거기서 각각의 원소를 시작으로 해서 연속한 원소들의 최대공약수가 $2$ 이상인 가장 긴 부분 수열의 길이를 투 포인터로 구한다.