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寫的報(bào)告說(shuō)是模擬，然后我模擬了以下，TLE了，然后開(kāi)始分析
7  * 兩個(gè)數(shù)a,b除完gcd(a,b)之后
8  * a == 1,b == 1,乘2之后向上推導(dǎo)
9  * a == 2,b == 2,的上一步只可能是a == 3,b == 1,之后繼續(xù)乘2向上導(dǎo)
10  * 可以發(fā)現(xiàn)只有a是b的
11  * 1 3 7 15 31 63 127

倍時(shí)能得出b == 0
12  * 此時(shí)把a(bǔ)+b必須是2的整數(shù)倍才行，而這個(gè)倍數(shù)就是答案
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) 評(píng)論(0) 編輯收藏引用所屬分類: 解題報(bào)告

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。


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

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

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

Why so serious? --[NKU]schindlerlee

2009年12月7日星期一.sgu126

導(dǎo)航

統(tǒng)計(jì)信息

News

留言簿(5)

隨筆分類(90)

隨筆檔案(105)

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜