题目：http://acm.hdu.edu.cn/showproblem.php?pid=1316
题意：给两个数a和b，其中它们可能很大，最大到10^100，然后求去区间[a,b]内有多少个fib数。
分析：这个题呢，看数据肯定是要当字符串处理的，那么对于本题我的思路就是先把fib数长度小于等于100的预处理出来。
然后呢，就与a和b比较，分别找出刚好大于等于a的fib数的下标和刚好小于等于b的fib数下标，假设分别是record1和
record2，那么record2-record1+1就是答案了。
估计了一下，由于在1000以内的fib数的长度就超过了100，所以预处理到1000个fib数就行了。
#include <iostream>
#include <string.h>
#include <stdio.h> using namespace std;
const int N=1005; int fib[N][105];
int f[N][105];
int h[N]; void Solve()
{
memset(fib,0,sizeof(fib));
h[0]=0;h[1]=0;
fib[0][0]=1;fib[1][0]=1;
for(int i=2;i<N;i++)
{
for(int j=0;j<105;j++)
{
fib[i][j]+=fib[i-1][j]+fib[i-2][j];
if(fib[i][j]>=10)
{
fib[i][j]-=10;
fib[i][j+1]++;
}
}
for(int j=104;j>=0;j--)
{
if(fib[i][j])
{
h[i]=j;
break;
}
}
}
} bool compare1(char *str,int len,int a[],int n)
{
if(n<len) return true;
if(n>len) return false;
for(int i=0;i<n;i++)
{
if(str[i]-'0'>a[i]) return true;
if(str[i]-'0'<a[i]) return false;
}
return true;
} bool compare2(char *str,int len,int a[],int n)
{
if(n>len) return true;
if(n<len) return false;
for(int i=0;i<n;i++)
{
if(str[i]-'0'<a[i]) return true;
if(str[i]-'0'>a[i]) return false;
}
return true;
} char a[105],b[105]; int main()
{
Solve();
for(int i=0;i<N;i++)
for(int j=h[i];j>=0;j--)
f[i][h[i]-j]=fib[i][j];
int record1,record2;
while(cin>>a>>b)
{
int len1=strlen(a);
int len2=strlen(b);
if(len1==1&&len2==1&&a[0]=='0'&&b[0]=='0') break;
for(int i=1;i<N;i++)
{
if(compare2(a,len1,f[i],h[i]+1))
{
record1=i;
break;
}
}
for(int i=N-1;i>=1;i--)
{
if(compare1(b,len2,f[i],h[i]+1))
{
record2=i;
break;
}
}
cout<<record2-record1+1<<endl;
}
return 0;
}