hdu 1316 How Many Fibs?

链接 给定两个数，问中间夹多少斐波那契数

这个题算是这次训练里最难的了>_<要二分，要字符串比较（而且还得自己写函数）

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char data[1070][107];///
char a[200],b[200];
int cmp_ab(char *s1,char *s2)
{
    for(int k=0;k<=105;k++)
    {
        if(k==105) return s1[k]-s2[k];
        if(s1[k]!=s2[k]) return s1[k]-s2[k];
    }
}
int find1(int i,char *x)
{
    int low=0,high=i,mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        int value=cmp_ab(x,data[mid]);
        if(value>0) low=mid+1;
        if(value==0) return mid-1;
        if(value<0) high=mid-1;
    }
    return high;//high<low
}
int find2(int i,char *x)
{
    int low=0,high=i,mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        int value=cmp_ab(x,data[mid]);
        if(value==0) return mid+1;
        if(value>0) low=mid+1;
        else high=mid-1;
    }
    return low;//low>high
}
int main()
{
    data[0][105]=1,data[1][105]=2;///
    int p=105,i=2;
    while(data[i-1][5]<=1)
    {
        for(int j=105;j>=p;j--)
        data[i][j]=data[i-1][j]+data[i-2][j];
        for(int j=105;j>=p;j--)
        {
            int c=data[i][j]/10;
            if(c>=1)
            {
                data[i][j]=data[i][j]%10;
                data[i][j-1]=data[i][j-1]+c;
            }
        }
        if(data[i][p-1]>0) p--;
        i++;
    }
    while(cin>>a>>b)
    {
        if(a[0]=='0'&&b[0]=='0') break;
        int len1=strlen(a)-1;
        int len2=strlen(b)-1;
        int k;
        for(int d=len1,k=105;d>=0;d--,k--)
        {
            a[k]=a[d]-'0';
            a[d]=0;
        }
        for(int d=len2,k=105;d>=0;d--,k--)
        {
            b[k]=b[d]-'0';
            b[d]=0;
        }
        int l=find1(i-1,a);
        int r=find2(i-1,b);
        cout<<r-l-1<<endl;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
    }
    return 0;
}