Educational Codeforces Round 117 X-Magic Pair 题解 (Java/C++)

题解

我们假设a<b，我们来观察各种可能的操作:

根据上图，我们发现，在0<a<b-2a时，a始终不会被替换掉，b会不断被b-a替代，直到存在某个c，使得b-(c+1)a<0且b-ca>0。
以第一步为例，假设我们将a:=b-a。那么第二步b-(b-a)=a。那么其结果要么是(a, b)要么是(a, b-a)。
同理我们发现只有(a, b-a)有可能进一步转化为(a, b-2a)、(a, b-3a)……

于是假设这样的一个c，使得b-(c+1)a<0且b-ca>0。从(a, b)到(a, b-ca)的这个过程中，可能产生的数字为：a, b, b-a, b-2a, ..., b-ca。而显然b-ca = b % a，因此b-ca < a。
于是我们重新以(b % a, a)为初始值，再次在所有可能的数字中寻找x即可。

代码

Java

C++