BOJ 12858 - Range GCD

image.png

검문 문제를 생각해보자. d=gcd(x1−0,x2−x1,x3−x1,… )d=gcd(x_1-0, x_2-x_1, x_3-x_1, \dots) 라고 하자.

그리고 xi % d=rx_i ~\%~ d=r 이라고 하자. 구간의 모든 ii 에 대해 rr 이 같아야 한다.

그럼 여기서 원래 최대공약수 gg 를 생각해보자.

g=gcd(d,r)g = gcd(d, r) 이 아닐까?

이대로 구현했더니 맞았다.

gcd(x1,x2,… )=gcd(x1,x2−x1,x3−x2,… )gcd(x_1,x_2,\dots)=gcd(x_1,x_2-x_1,x_3-x_2,\dots) 를 이용해서 푸는 문제라고 한다.

비슷하게 생각해서 맞을 수 있었다.

Tags:

Categories:

Updated:

Comments

You may also enjoy