Posted on 2008-09-03 16:19
Hero 閱讀(153)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //2413 Accepted 880K 32MS G++ 3264B PKU
2
3 #include <iostream>
4 #include <cmath>
5 using namespace std;
6
7 const int Base=1000000000;
8 const int Capacity=200;
9 typedef long long llong;
10
11 struct BigInt{
12 int Len;
13 int Data[Capacity];
14 BigInt():Len(0){}
15 BigInt(const BigInt &V):Len(V.Len){memcpy(Data,V.Data,Len*sizeof*Data);}
16 BigInt(int V):Len(0){for(;V>0;V/=Base) Data[Len++]=V%Base;}
17 BigInt &operator=(const BigInt &V){Len=V.Len;memcpy(Data,V.Data,Len*sizeof*Data);return *this;}
18 int &operator[](int Index){return Data[Index];}
19 int operator[](int Index)const{return Data[Index];}
20 };
21 int compare(const BigInt &A,const BigInt &B){
22 if(A.Len!=B.Len) return A.Len>B.Len ? 1:-1;
23 int i;
24 for(i=A.Len-1;i>=0 && A[i]==B[i];i--);
25 if(i<0)return 0;
26 return A[i]>B[i] ? 1:-1;
27 }
28 BigInt operator+(const BigInt &A,const BigInt &B){
29 int i,Carry(0);
30 BigInt R;
31 for(i=0;i<A.Len||i<B.Len||Carry>0;i++){
32 if(i<A.Len) Carry+=A[i];
33 if(i<B.Len) Carry+=B[i];;
34 R[i]=Carry%Base;
35 Carry/=Base;
36 }
37 R.Len=i;
38 return R;
39 }
40 BigInt operator-(const BigInt &A,const BigInt &B){
41 int i,Carry(0);
42 BigInt R;
43 R.Len=A.Len;
44 for(i=0;i<R.Len;i++){
45 R[i]=A[i]-Carry;
46 if(i<B.Len) R[i]-=B[i];
47 if(R[i]<0) Carry=1,R[i]+=Base;
48 else Carry=0;
49 }
50 while(R.Len>0&&R[R.Len-1]==0) R.Len--;
51 return R;
52 }
53 BigInt operator*(const BigInt &A,const int &B){
54 int i;
55 llong Carry(0);
56 BigInt R;
57 for(i=0;i<A.Len||Carry>0;i++){
58 if(i<A.Len) Carry+=llong(A[i])*B;
59 R[i]=Carry%Base;
60 Carry/=Base;
61 }
62 R.Len=i;
63 return R;
64 }
65 istream &operator>>(istream &In,BigInt &V){
66 char Ch;
67 for(V=0;In>>Ch;){
68 V=V*10+(Ch-'0');
69 if(In.peek()<=' ') break;
70 }
71 return In;
72 }
73 ostream &operator<<(ostream &Out,const BigInt &V){
74 int i;
75 Out<<(V.Len==0 ? 0:V[V.Len-1]);
76 for(i=V.Len-2;i>=0;i--) for(int j=Base/10;j>0;j/=10) Out<<V[i]/j%10;
77 return Out;
78 }
79
80
81 BigInt Bint0(0) ;
82 BigInt Bint1(1) ;
83
84 BigInt ina, inb ;
85
86 const int size = 600 ;
87 BigInt fib[size] ;
88
89 void process()
90 {
91 int left = 1; int right = size-1 ; int mid ;
92
93 while( left < right )
94 {
95 mid = (left+right)>>1 ;
96 if( compare(fib[mid], ina) >= 0 ) right = mid ;
97 else left = mid + 1 ;
98 }
99 //if( compare(fib[right], ina) >= 0 ) left = right ;
100
101 int sn = right ;
102
103 left = sn ; right = size-1 ;
104
105 while( left < right )
106 {
107 mid = ((left+right)/2) ;
108 if( compare(fib[mid], inb)<=0 ) left = mid+1 ;
109 else right = mid ;
110 }
111 //if( compare(fib[right], inb)<=0 ) left = right ;
112
113 int en = right ;
114
115
116 printf( "%d\n", en - sn ) ;
117 }
118
119 void process1()
120 {
121 int sn = 1 ; int en ;
122
123 for( ; sn<size; sn++ )
124 {
125 if( compare(fib[sn], ina)>= 0 ) break ;
126 }
127 for( en=sn; en<size; en++ )
128 {
129 if( compare(fib[en], inb)>0 ) break ;
130 }
131
132 printf( "%d\n", en-sn ) ;
133 }
134
135 int main()
136 {
137 //cout << Bint0 << Bint1 << endl ;
138
139 fib[1] = Bint1 ; fib[2] = Bint1 * 2 ;
140 for( int i=3; i<size; i++ )
141 {
142 fib[i] = fib[i-2] + fib[i-1] ;
143 }
144
145 while( cin>>ina>>inb )
146 {
147 //cout << ina << inb << endl ;
148 if( compare(ina, Bint0)==0 && compare(inb, Bint0)==0 ) break ;
149
150 process() ;
151
152 //output() ;
153 }
154
155 return 0 ;
156 }