BOJ 17433 - 신비로운 수

모든 i번째 수에 대하여 나머지 R이 되도록 하는 숫자를 구하는 문제이다.

i번째 수를 M으로 나누었을때를 식으로 표현하면 다음과 같이 나타낼 수 있다.

$N_i=MQ_i+R$

첫번째 수와 두번째 수를 M으로 나눈 항등식으로 표현하면 아래와 같다.

$N_1=MQ_1+R$

$N_2=MQ_2+R$

두 수를 빼면

$N_1-N_2=(Q_1-Q_2)M$

와 같이 나타낼 수 있다.

인접한 수들에 대해 전부 해보면

$N_1-N_2=(Q_1-Q_2)M$

$N_2-N_3=(Q_2-Q_3)M$

$N_3-N_4=(Q_3-Q_4)M$

$N_4-N_5=(Q_4-Q_5)M$

...

$N_{n-1}-N_n=(Q_{n-1}-Q_n)M$

위 식을 토대로 인접한 두 수의 차의 GCD값이 구하고자 하는 M의 값임을 알 수 있다.

주어진 모든 수가 같다면 M은 무한개로 존재할 수 있다.