数学题：
给你一个区间[a,b]在该区间内有多少个费波那列数（包括a，b），数据规模达到10^100。
这题的原理很简单，基本没什么算法，其实更偏重于编程能力，需要用到高精度。另外找区间的地方要小心
1.先把长度在100以内的fibs先找出来并保存，再开始输入case
2.得到区间[a,b]，那么在保存下来的fibs里找到 第一个f[p],要满足a<=f[p] , 然后继续找下去，找到 第一个f[q],满足b<=f[q]
其中f[q]还要处理一下，如果b=f[q]，那么f[q]显然在区间内 ； b<f[q]，那说明f[q]并不在区间内，由于是第一个所以可以知道f[q-1]一定要区间内而且f[q-1]<b , 处理后就可以得到准确的q值
最后答案就是q-p+1
代码又写得不好，最近脑袋比较乱写出来的代码都很乱
//构建10^100以内的fibs数 #include <cstdio> #include <cstring> #define LEN 150 #define MAX 510 struct fibs {int a[LEN],len; }f[MAX];int find(struct fibs x ,struct fibs y) {//当x<y为1，x>y为-1,相等为0if(x.len < y.len) return 1;else if(x.len > y.len) return -1;int i=x.len-1 , j=y.len-1;while(i>=0){if(x.a[i] < y.a[j]) return 1;else if(x.a[i] > y.a[j]) return -1;i--; j--;}return 0; } void add(int x ,int y ,int m) //f[x]>f[y] {int t,c=0;for(int i=0; i<f[x].len; i++){t=f[x].a[i]+f[y].a[i]+c;f[m].a[i]=t%10;c=t/10;}f[m].len=f[x].len;if(c){f[m].a[f[m].len]=c;f[m].len++;}return ; } void init() {memset(f,0,sizeof(f[0]));f[1].a[0]=1; f[1].len=1;f[2].a[0]=2; f[2].len=1;int i=3;do{add(i-1,i-2,i);if(f[i].len>=101) break;i++;}while(1);//printf("count=%d len=%d\n",i,f[i].len);return ; } int main() {init();char s1[LEN],s2[LEN];struct fibs a,b;while(scanf("%s%s",s1,s2)!=EOF){if(!strcmp(s1,"0") && !strcmp(s2,"0")) break;a.len=strlen(s1); b.len=strlen(s2);int i,j,p,q,t;for(i=0,j=a.len-1; i<a.len; i++,j--)a.a[j]=s1[i]-'0';for(i=0,j=b.len-1; i<b.len; i++,j--)b.a[j]=s2[i]-'0';//for(i=0; i<a.len; i++) printf("%d",a.a[i]); printf("\n");//for(i=0; i<b.len; i++) printf("%d",b.a[i]); printf("\n"); i=1;while(1){ t=find(a,f[i]);if(t==1 || t==0) break;i++;}p=i;while(1){t=find(b,f[i]);if(t==1 || t==0) break;i++;}if(t==1) q=i-1;else q=i;//printf("p=%d q=%d\n",p,q);//for(int i=f[p].len-1; i>=0; i--) printf("%d",f[p].a[i]); printf("\n");//for(int i=f[q].len-1; i>=0; i--) printf("%d",f[q].a[i]); printf("\n");printf("%d\n",q-p+1);}return 0 ; }
