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

Submission #136897997 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #136898617 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论