hdu1316 斐波纳契大数二分

hdu1316

[cpp]
#include
#include
#include
#include
using namespace std;

char a[105],b[105];
char F[495][110];

int cmp(char a[],char b[])
{
int lenA=strlen(a),lenB=strlen(b),i,j;
if(lenA

     // if(lenB>lenA)   return -1;    bug

if(lenB=0;i--){if(a[i]b[i]) return -1;}return 0;}int bsearch_preTOx(char x[]){int mid,low=1,high=490;while(low low-1;}int bsearch_nextTOx(char x[]){int mid,low=1,high=490;while(low=0) low=mid;else high=mid-1;}return high+1;}void upsidedown(char x[]){int len=strlen(x);for(int i=0;i main(){int i,j,k,len;F[1][0]='1';F[1][1]='\0';F[2][0]='2';F[2][1]='\0';for(i=3;i<=495;i++){len=strlen(F[i-2]);for(j=0;j'0'+9){F[i][j]-=10;F[i][j+1]++;}}if(F[i][len]=='0')
F[i][len]='\0';}while(scanf("%s%s",a,b)!=EOF){if(a[0]=='0'&&b[0]=='0') break;upsidedown(b);upsidedown(a);// for(i=1;i<=490;i++) if(cmp(a,F[i])>=0) break;// for(j=490;j>=1;j--) if(cmp(b,F[j])<=0) break;// printf("%d %d %d\n",i-1,j+1,j-(i-1));printf("%d\n",bsearch_nextTOx(b)-1-bsearch_preTOx(a));}return
0;}

hdu1316 斐波纳契 大数 二分