Boxes

题目描述

There are two boxes. There are $A$ balls in the first box, and $B$ balls in the second box. It is possible to move balls from one box to another. From one box into another one should move as many balls as the other box already contains. You have to determine, whether it is possible to move all balls into one box.

题意概述

给定两个数$A$和$B$，每次操作可以将两个数中较大的数减去较小的数，再将较小的数翻倍。问至少经过多少次操作后两个数中有一个为$0$，若不可能则输出$-1$。

数据范围：$1 \le A+B \le 2147483647$。

算法分析

可以发现在任何时候，将两个数同时除以它们的最大公约数并不会影响答案；若两个数的和为奇数，则永远不可能结束。基于以上两点，答案不会超过$\log(A+B)$，因此直接模拟即可。