BOJ 12858 - Range GCD
검문 문제를 생각해보자. $d=gcd(x_1-0, x_2-x_1, x_3-x_1, \dots)$ 라고 하자.
그리고 $x_i ~\%~ d=r$ 이라고 하자. 구간의 모든 $i$ 에 대해 $r$ 이 같아야 한다.
그럼 여기서 원래 최대공약수 $g$ 를 생각해보자.
$g = gcd(d, r)$ 이 아닐까?
이대로 구현했더니 맞았다.
$gcd(x_1,x_2,\dots)=gcd(x_1,x_2-x_1,x_3-x_2,\dots)$ 를 이용해서 푸는 문제라고 한다.
비슷하게 생각해서 맞을 수 있었다.
Comments