POJ 2413 How many Fibs?#二分+大数加法

http://poj.org/problem?id=2413

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

//到第485个fib数才有100位

const int LAST=108;

char res[500][110]; //存储fib数

char *pos[500]; //存储每个fib数的首地址

char* Addition(char *a,char *b,char *sum)

{

    int i,j,k,first;

    //逆序开始，暂不处理进位

    for(i=strlen(a)-1,j=LAST;i>=0;i--,j--)

        sum[j]=a[i]-'0';

    for(i=strlen(b)-1,k=LAST;i>=0;i--,k--)

        sum[k]+=b[i]-'0';

    //获取sum结果的首位位置

    first=(j<k?j:k);

    //处理进位

    for(i=LAST;i>=first;i--)

    {

        sum[i-1]+=sum[i]/10;

        sum[i]=sum[i]%10+'0';

    }

    //去除前导0

    while(sum[first]=='0'&&first<LAST)

        first++;

    //返回sum的首位地址

    return &sum[first];

}

//计算fib数

void fib()

{

    memset(res,0,sizeof(res));

    memset(pos,NULL,sizeof(pos));

    strcpy(res[1],"1");

    strcpy(res[2],"2");

    pos[1]=res[1];

    pos[2]=res[2];

    for(int i=3;i<485;i++)

        pos[i]=Addition(pos[i-2],pos[i-1],res[i]);

}

int cmp(char *a,char *b)

{

    int lena=strlen(a),lenb=strlen(b);

    if(lena==lenb)

        return strcmp(a,b);

    return lena>lenb?1:-1;

}

int binarySearch(char *num,bool &flag)

{

    int l=1,r=480;

    while(l<=r)

    {

        int mid=(l+r)/2;

        int res=cmp(num,pos[mid]);

        if(res==0)

        {

            flag=true;

            return mid;

        }

        else if(res<0)

            r=mid-1;

        else l=mid+1;

    }

    return l;

}

int main()

{

    fib();

    char a[105],b[105];

    while(scanf("%s %s",a,b)!=EOF)

    {

        if(strcmp(a,"0")==0&&strcmp(b,"0")==0)

            break;

        bool flagL=false,flagR=false;

        int l=binarySearch(a,flagL);

        int r=binarySearch(b,flagR);

        //返回值是[1,a)和[1,b)内的fib个数，所以若b也是fib数，输出时需+1

        if(flagR)

            printf("%d\n",r-l+1);

        else printf("%d\n",r-l);

    }

    return 0;

}