hdu1316 斐波纳契 大数 二分

hdu1316

[cpp] 
#include<iostream> 
#include<cstring> 
#include<cstdio> 
#include<algorithm> 
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<lenB)    return 1; 
<pre name="code" class="cpp">     // if(lenB>lenA)   return -1;    bug</pre>  if(lenB<lenA) return -1;for(i=lenA-1;i>=0;i--){if(a[i]<b[i]) return 1;if(a[i]>b[i]) return -1;}return 0;}int bsearch_preTOx(char x[]){int mid,low=1,high=490;while(low<high){mid=low+(high-low)/2;if(cmp(F[mid],x)<=0) high=mid;else low=mid+1;}return 
 low-1;}int bsearch_nextTOx(char x[]){int mid,low=1,high=490;while(low<high){mid=low+(high-low+1)/2;if(cmp(F[mid],x)>=0) low=mid;else high=mid-1;}return high+1;}void upsidedown(char x[]){int len=strlen(x);for(int i=0;i<len/2;i++) swap(x[i],x[len-i-1]);}int 
 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<len;j++){F[i][j]=F[i-1][j]+F[i-2][j]-'0';}j=len;len=strlen(F[i-1]);for(;j<len;j++) F[i][j]=F[i-1][j];F[i][len]='0';F[i][len+1]='/0';for(j=0;j<len;j++){if(F[i][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;}<p></p> 
<pre></pre> 
<br> 
<br> 
<p></p>