http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1001&cid=14568&hide=0
View Code
1 #include<iostream>
2 #include<cmath>
3 using namespace std;
4 int cont(int n)//1000886
5 {
6 int i,sum;
7 int temp;//long long temp;
8 sum=(n/2)*2;
9 for(i=1;(temp=pow(4,i))<n;i++)
10 {
11 sum+=((n-1)/temp+1)/2*2;
12 }
13 return sum+1;
14 }
15 int fast(int n)
16 {
17 int sum=n/2+1,t;
18 int mid,l=1,r=2*n;
19 while(l<r)
20 {
21 mid=(r+l)>>1;
22 t=mid;
23 while(t%4==0) t/=4;
24 if(t%2==1) t=cont(mid);
25 else {t=cont(mid-1);mid--;}
26 if(t==n) return mid;
27 else if(t>n)
28 {
29 r=mid;
30 }
31 else
32 {
33 l=mid+1;
34 }
35 }
36 return 0;
37 }
38 int main()
39 {
40 int n,t;
41 cin>>t;
42 while(t--)
43 {
44 cin>>n;
45 if(n%2)
46 cout<<fast(n)<<endl;
47 else
48 cout<<2*fast(n-1)<<endl;
49 }
50 return 0;
51 }