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 閱讀(949) 評論(0) 編輯收藏引用所屬分類: 解題報告

只有注冊用戶登錄后才能發表評論。


相關文章: zju2589 不重合的n個圓形成的區域 pku3334 二分+求多邊形面積 hdu3264 二分+求兩圓交的面積 zoj2107 最近點對，分治 pku1819 幾何+模擬不難，但是不容易寫對 codeforces contest 16 problem E 比較容易的狀態壓縮動態規劃。 2010-06-21 20:10:05 關于Aho-Corasick (AC) 自動機的三道題目 2010-06-16 12:04:40 pku3528 三維凸包 2010-06-11 00:40 spoj1182 ,dp, number theory, binary search 數位類統計問題 2010-06-08 23:24:36.ural1057 number theory and dp

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

Why so serious? --[NKU]schindlerlee

2009年12月7日星期一.sgu126

導航

統計信息

News

留言簿(5)

隨筆分類(90)

隨筆檔案(105)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜