백준 12858 : Range GCD

우리는 $a_x$~$a_y$의 구간 gcd를 다음과 같이 나타낼 수 있다.

$gcd(a_x, a_{x+1}, a_{x+2}, ... , a_y)$

$=gcd(a_x, a_{x+1}-a_x, a_{x+2}-a_{x+1}, ..., a_y-a_{y-1})$

 

여기서 우리는 $a_k-a_{k-1}$꼴의 항들과 $a_k$꼴의 항 2가지를 세그먼트 트리를 이용해 관리할 수 있다.

 

만약 $a_2$~$a_4$ 구간에 range update $+k$가 일어났다고 가정해보자.

 

$a_k-a_{k-1}$꼴의 항들의 변화이다. 

$((a_2 + k) -a_1, (a_3 + k) -(a_2+k), (a_4+k)-(a_3+k), a_5-(a_4+k)..., a_n-a_{n-1})$

$=(k+a_2-a_1, a_3-a_2, a_4-a_3,-k+a_5-a_4,..., a_n-a_{n-1})$

$a_2-a_1$번 항과 $a_5-a_4$번 항만 $+k$, $-k$의 업데이트가 있었음을 알 수 있다.

 

결론

$[l,r]$구간에 $+k$ 업뎃이 들어온 경우 레이지로 $a_l$~$a_r$에 +k를 더해주고, gcd 세그멘트 트리에는 $a_l$엔 $+k$, $a_r$엔 $-k$를 더해준다. 

 

$[l,r]$구간의 gcd 쿼리는 $a_l$과 gcd 세그멘트 트리로 $a_{l+1}-a_l$, ... ,$a_r-a_{r-1}$의 gcd를 구한뒤, 두 값의 gcd를 구해준다.