HDU 1316 大数二分

建素数表 ?二分查找 ?练手用了。。

#include "stdio.h"
#include "string.h"
int f[5010][1010];

int pk(int a[],int b[])
{
    int i;
    if (a[0]>b[0]) return 1;
    if (a[0]<b[0]) return -1;

    for (i=a[0];i>=1;i--)
    {
        if (a[i]>b[i]) return 1;
        if (a[i]<b[i]) return -1;
    }
    return 0;

}

int fi(int x[],int op)
{
    int l,r,mid,key;
    l=1;r=5000;
    while (l<=r)
    {
        mid=(l+r)/2;
        key=pk(x,f[mid]);
        if (key==1) l=mid+1;
        else if (key==-1) r=mid-1;
        else return mid;
    }

    if (op==1) return l;
    if (op==2) return r;
}

int main()
{
    int i,j,lea,leb,keya,keyb;
    int a[1201],b[1201];
    char stra[1201],strb[1201];
    memset(f,sizeof(f));
    f[1][0]=f[1][1]=f[2][0]=f[2][1]=1;
    for (i=3;i<=5000;i++)
    {
        for (j=1;j<=f[i-1][0];j++)
        f[i][j]=f[i-1][j]+f[i-2][j];
        f[i][0]=f[i-1][0];
        for (j=1;j<=f[i][0];j++)
        {
            f[i][j+1]+=f[i][j]/10;
            f[i][j]%=10;
        }
        if (f[i][f[i][0]+1]!=0) f[i][0]++;
    }
  //  printf("%dn",f[5000][0]);

    while (scanf("%s",stra)!=EOF)
    {
        scanf("%s",strb);
        if (stra[0]=='0' && strb[0]=='0') break;
        if (stra[0]=='0') stra[0]='1';
        a[0]=lea=strlen(stra);
        b[0]=leb=strlen(strb);
        for (i=0;stra[i];i++)
            a[lea-i]=stra[i]-'0';
        for (i=0;strb[i];i++)
            b[leb-i]=strb[i]-'0';

        keya=fi(a,1);
        keyb=fi(b,2);
        printf("%dn",keyb-keya+1);
    }

    return 0;

}