题目大意：
问[s,e]之间有多少个 斐波那契数。
思路分析：
直接模拟高精度字符串的加法和大小的比較。
注意wa点再 s 能够从 0 開始
那么要在推断输入结束的时候注意一下。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm> using namespace std; struct node
{
char str[111];
int len; void print()
{
for(int i=len-1; i>=0; i--)
{
printf("%c",str[i]);
}
puts("");
} } fib[1500]; node operator + (const node &a,const node &b)
{
node c;
for(int i=0; i<=110; i++)c.str[i]='0';
for(int i=0; i<max(a.len,b.len); i++)
{
int dig=c.str[i]-'0'+a.str[i]-'0'+b.str[i]-'0';
int s=0;
if(dig>=10)
{
dig-=10;
s++;
}
c.str[i]=dig+'0';
if(s)c.str[i+1]='1';
}
for(c.len=110; c.str[c.len]=='0' ; c.len--);
c.len++;
return c;
}
bool operator <= (node &a,node &b)
{
if(a.len!=b.len)return a.len<b.len;
else
{
for(int i=a.len-1; i>=0; i--)
{
if(a.str[i]>b.str[i])
return false;
else if(a.str[i]<b.str[i])
return true;
}
return true;
}
} bool operator < (node &a,node &b)
{
if(a.len!=b.len)return a.len<b.len;
else
{
bool is=true; for(int i=0; i<a.len; i++)
if(a.str[i]!=b.str[i])is=false; for(int i=a.len-1; i>=0 && !is; i--)
{
if(a.str[i]>b.str[i])
return false;
else if(a.str[i]<b.str[i])
return true;
}
return !is;
}
} int main()
{
fib[1].len=1;
fib[1].str[0]='1';
fib[2].len=1;
fib[2].str[0]='2';
for(int i=3;; i++)
{
fib[i]=fib[i-1]+fib[i-2];
if(fib[i].len>101)break;
} node s,e;
while(scanf("%s%s",s.str,e.str)!=EOF)
{
if(s.str[0]=='0' && e.str[0]=='0')break;
s.len=strlen(s.str);
e.len=strlen(e.str);
reverse(s.str,s.str+s.len);
reverse(e.str,e.str+e.len);
int i=1,st,ed;
while(fib[i]<s)i++;
st=i;
while(fib[i]<=e)i++;
ed=i;
printf("%d\n",ed-st);
}
return 0;
}