SGU 126 - Boxes

Description

There are two boxes. There are $A$ balls in the first box, and $B$ balls in the second box ($0 < A + B < 2147483648$). 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.

Input

The first line contains two integers $A$ and $B$, delimited by space.

Output

First line should contain the number $N$ - the number of moves which are required to move all balls into one box, or -1 if it is impossible.

Sample Input

 1  2 6 

Sample Output

 1  2 

Analysis

数学法

$K$$(N, 0) K - 1$$(N / 2, N / 2)$
$K - 2$$(N / 4, 3N / 4) K - 3$$(N / 8, 7N / 8), (5N / 8, 3N / 8)$
$K - 4$$(N / 16, 15N / 16), (9N / 16, 7N / 16), (5N / 16, 11N / 16), (13N / 16, 3N / 16) \cdots$$\cdots$

Solution

模拟法

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23  #include using namespace std; const int MAX = 32; int main() { int x, y; while(cin >> x >> y) { int nCnt = 0; while(x != 0 && y != 0 && nCnt <= MAX) { if(x <= y) { y -= x; x += x; } else { x -= y; y += y; } nCnt++; } if(x != 0 && y != 0) { cout << -1 << endl; } else { cout << nCnt << endl; } } return 0; } 

数学法

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30  #include using namespace std; int gcd(int x, int y); int main() { int x, y; while(cin >> x >> y) { int nCnt = 0; int nTmp = gcd(x, y); x /= nTmp; y /= nTmp; int nSum = x + y; while(nSum > 1) { if(nSum & 1) { nCnt = -1; break; } else { nCnt++; nSum >>= 1; } } if(x == 0 || y == 0) { nCnt = 0; } cout << nCnt << endl; } } int gcd(int x, int y) { if(y == 0) { return x; } else { return gcd(y, x % y); } }