Educational Codeforces Round 117 (Rated for Div. 2) D. X-Magic Pair

Problem - D - Codeforces

a와 b가 주어지고 |a-b| 를 a 또는 b로 계속 교체하는데 도중에 x가 등장하는지 판단하는 문제다.

일단 |a-b| 를 a와 b 중 큰 수와 교체를 해야 한다.

작은 수와 교체를 해 보면 숫자가 계속 반복된 다는 것을 알 수 있다.

결국 a b 중 큰 수와 |a-b|를 계속 교체해야 한다는 것을 알 수 있다.

하지만 일일이 교체하다 보면 시간이 너무 오래 걸린다.

교체를 건너뛸 수 있는 경우가 존재한다.

a b 중 b 가 a보다 100배 이상 큰 수라고 가정하자

그러면 b는 계속 b-a로 교체가 될 것이고 이는 b에서 계속 a를 빼는 결과와 같다.

b가 a보다 작아질 때까지 b에서 a를 빼므로 도중에 x가 나오는지 판별할 때는

x%a 가 b%a와 같은지만 판별하면 된다.

판별한 후에는 바로 a, b = b% a, a로 건너뛰어주면 된다.

항상 x의 값이 1 <= x <= max(a, b) 사이에 존재해야 하므로x > max(a, b)  이면 답은 no이다.

여기서는 b가 a보다 큰 수로 가정했으니까 x 가 b보다 커지면 no이다.

만약 x가 a <= x <= b에 존재하지 않고 x < a 가 되면 어떻게 될까?

똑같이 x%a 와 b%a를 비교해 줘도 되고 안 해줘도 된다.

왜냐하면 b%a 가 x가 된다는 뜻은 b %= a에서 b가 실제로 x가 되기 때문에 다음 루프에서 x가 등장하게 된다.