/*
How many Fibs?
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 7752 Accepted: 2856
Description
* Recall the definition of the Fibonacci numbers:
* f1 := 1
* f2 := 2
* fn := fn-1 + fn-2 (n>=3)
*
* Given two numbers a and b, calculate how many Fibonacci numbers
* are in the range [a,b].
Input
* The input contains several test cases. Each test case consists of two
* non-negative integer numbers a and b. Input is terminated by a=b=0.
* Otherwise, a<=b<=10100. The numbers a and b are given with no
* superfluous leading zeros.
Output
* For each test case output on a single line the number of Fibonacci
* numbers fi with a<=fi<=b.
Sample Input
10 100
1234567890 9876543210
0 0
Sample Output
5
4
Source
Ulm Local 2000
分析：当高精度与字符串练习~~
*/
#include<iostream> #include<string> using namespace std; int num[501][201]={0}; void cal(int z) { int x=z-2,y=z-1; for(int i=1;i<=num[y][0];++i)num[z][i]=num[x][i]+num[y][i]; for(int i=1;i<=num[y][0];++i) { num[z][i+1]+=num[z][i]/10; num[z][i]%=10; } num[z][0]=num[y][0]; if(num[z][num[z][0]+1]>0)++num[z][0]; } int find(int x) { int l=1,r=500,m; while(l<r) { m=(l+r)>>1; if(num[m][0]==x)return(m); if(num[m][0]>x) r=m-1; else l=m+1; } return(l); } bool amb(string a,string b) { if(a.size()>b.size())return(true); if(a.size()<b.size())return(false); for(int i=0;i<a.size();++i) if(a[i]>b[i])return(true); else if(a[i]<b[i])return(false); return(false); } int main() { //freopen("car.in","r",stdin); //freopen("car.out","w",stdout); char s1[101],s2[101]; string a,b,fib[501]; int l,r; num[1][0]=1; num[1][1]=1; num[2][0]=1; num[2][1]=2; for(int i=3;i<501;++i) { cal(i); for(int j=num[i][0];j>0;--j) fib[i]+=((char)num[i][j]+'0'); } fib[1]="1"; fib[2]="2"; while(scanf("%s%s",s1,s2)) { a=s1;b=s2; if((a=="0")&&(b=="0"))break; l=find(a.size()); r=find(b.size()); while(amb(fib[l],a))--l; while(amb(a,fib[l]))++l; while(amb(b,fib[r]))++r; while(amb(fib[r],b))--r; cout<<r-l+1<<endl; } return 0; }
