Why so serious? --[NKU]schindlerlee

2009年12月7日星期一.sgu126

 1 /*
 2  * SOUR:sgu126
 3  * ALGO:模拟
 4  * DATE: 2009年 12月 07日 星期一 00:29:29 CST
 5  * COMM:3
 6  * 看ACRush写的报告说是模拟，然后我模拟了以下，TLE了，然后开始分析
 7  * 两个数a,b除完gcd(a,b)之后
 8  * a == 1,b == 1,乘2之后向上推导
 9  * a == 2,b == 2,的上一步只可能是a == 3,b == 1,之后继续乘2向上导
10  * 可以发现只有a是b的
11  * 1 3 7 15 31 63 127 倍时能得出b == 0
12  * 此时把a+b必须是2的整数倍才行，而这个倍数就是答案
13  * */
14 #include<iostream>
15 #include<cstdio>
16 #include<cstdlib>
17 #include<cstring>
18 #include<algorithm>
19 using namespace std;
20 typedef long long LL;
21 const int maxint = 0x7fffffff;
22 const long long max64 = 0x7fffffffffffffffll;
23 
24 int gcd(int a, int b)
25 {
26     if (b == 0) return a;
27     return gcd(b,a%b);
28 }
29 
30 int a,b;
31 int main()
32 {
33     int i,j,k;
34     cin >> a >> b;
35     if(a < b) { swap(a,b); }
36     int tmp = gcd(a,b),sum,bit = 0,idx = 0;
37     a /= tmp,b /= tmp;
38     sum = a + b;
39     for(i = 0;i < 32;i++) {
40         if(sum &(1 << i)) {
41             bit ++;
42             idx = i;
43         }
44     }
45     if(bit == 1) {
46         printf("%d\n",idx);
47     }else {
48         printf("-1\n");
49     }
50     return 0;
51 }
52 
53 
54 

posted on 2009-12-07 01:31 schindlerlee 阅读(931) 评论(0)  编辑 收藏 引用 所属分类: 解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理