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>
补充：软件开发 , C++ ,
