How Many Fibs?
Adolfo_North
·
·
题解
这道题的核心是高精，但是拿数组存结果在比较的时候很麻烦，所以我不打算用数组。
那怎么办呢？我们发现，数据范围只有 10^{100}，完全可以把 100 位内的所有斐波那契数列的数打出来，通俗一点来说，就是打表。
#### 1.生成 $100$ 位内的所有斐波那契数列的数:
```cpp
#include<iostream>
#include<cstring>
using namespace std;
int c[110],d[110],e[110];//将数组不断滚动，所以只开3个
int main()
{
int lc=1,ld=1,le=1,cnt=2;//lc,ld,le记录数组长度,cnt记录一共有多少个数
d[0]=1;//初始化
e[0]=2;
cout<<'"'<<1<<'"'<<','<<'"'<<2<<'"'<<',';
while(1){
if(lc>100) break;
cnt++;
int jin=0;//来计算加法时的进位
lc=max(ld,le);
for(int i=0;i<lc;i++)
{
c[i]=d[i]+e[i]+jin; //记得加上进位
jin=c[i]/10;//计算进位
c[i]=c[i]%10;
}
if(jin>0)//最高位仍有进位
{
c[lc++]=jin;
}
//为了搭配字符串，在输出前和输出和加上引号
cout<<'"';
for(int i=lc-1;i>=0;i--)cout<<c[i];
cout<<'"'<<',';
//开始愉快的滚动
le=lc;
ld=le;
memcpy(d,e,sizeof(d));//数组复制
memcpy(e,c,sizeof(e));
}
cout<<endl<<endl<<cnt;//最后输出个数
return 0;
}
```
[输出结果（好多）](https://www.luogu.com.cn/problem/U243561)，在样例输出中复制。
一共 $480$ 个，直接把上面的复制下来放到字符串数组里就好了。
像这样：
```cpp
a[480]={"1","2","3"......};
```
##### 总算可以打表了，数组内打表结果省略好多，不要复制：
```cpp
#include<iostream>
using namespace std;
string a[480]={"1","2","3",省略一大片};
int main()
{
string f,b;
while(cin>>f>>b){
if(f[0]=='0'&&b[0]=='0') return 0;
int cnt=0;
for(int i=0;i<=480;i++){
if(a[i].size()>b.size()||(a[i].size()==b.size()&&a[i]>b)) break;//若当前位数大于b的位数，或当前数字大于b，退出循环
if(a[i].size()<f.size()||(a[i].size()==f.size()&&a[i]<f)) continue;//若当前位数小于f的位数，或当前数字小于f，进行下一次循环
cnt++;
}
cout<<cnt<<endl;
}
return 0;
}
```