Posted on 2010-12-03 15:23
Hero 閱讀(526)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1
//SGU 126 .CPP_VS Accepted 22 ms 0 kb
2
3
/**//*
4
126. Boxes
5
6time limit per test: 0.50 sec.
7memory limit per test: 4096 KB
8
9
10There 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.
11
12
13Input
14
15The first line contains two integers A and B, delimited by space.
16
17
18Output
19
20First 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.
21
22
23Sample Input
24
25Sample Output
26
272 6
28
29
30Sample Output
31
322
33
*/
34
35//如果log(2, (a+b)/gcd(a, b))是整數,那么它就是答案;否則無解.
36
37#include <iostream>
38#include <string>
39#include <set>
40using namespace std;
41typedef __int64 llong;
42int answer;
43
44llong fgcd( llong a, llong b )
45
{
46 if( 0 == a ) return b;
47 else
48 return fgcd( b%a, a );
49}
50
51int main()
52{
53#ifdef _ACM_
54 //freopen( "data.in", "r", stdin ) ;
55 //freopen( "data.out", "w", stdout ) ;
56#endif
57 llong ina, inb;
58
59 while( cin >> ina >> inb )
60
{
61 answer = -1 ;
62
63 if( ina < 0 || inb < 0 )
64 {
65 answer = -1;
66
}
67 else if( ina == 0 || inb == 0 )
68 {
69 answer = 0;
70 }
71 else
72 {
73 llong gcdvalue = fgcd(ina, inb);
74 ina = ina / gcdvalue;
75 inb = inb / gcdvalue;
76
77 llong sum = ina + inb;
78 for( int i=1; i<60; i++ )
79 {
80 llong pow2 = 1 << i;
81 if( pow2 == sum )
82 {
83 answer = i; break;
84 }
85 else if( pow2 > sum )
86 {
87 break;
88 }
89 }
90 }
91
92 printf( "%d\n", answer );
93 }
94
95 return 0;
96}
97