题解：UVA10183 How Many Fibs?

对于一个 C++ 选手，一看数据范围就知道要用高精度来写。

先来考虑一个弱化版

满足 $a,b \le 10^8$。

因为要求出两数之间的斐波那契数的个数，所以我们可以预处理出 $10^8$ 以内的斐波那契数。

1 2	f[1] = 1,f[2] = 1; for (...) 递推过程

然后就是找到第一项 $\ge a,b$ 的斐波那契数，并记录它的项数，然后相减就能得出答案。根据数据范围很容易排除暴力搜索，因此我们可以采用效率更高的二分答案。

设一共有 $n$ 个斐波那契数，要求出与第一项 $\ge m$ 的斐波那契数。因此可以将第 $k$ 项斐波那契数分成三种情况：

$f[k] > m$，继续在 $1 \sim k$ 的范围内查找；
$f[k] = m$，返回 $k$；
$f[k] < m$，继续在 $k + 1 \sim n$ 的范围内查找。

进阶版高精度

满足 $a,b \le 10^{100}$。

有了上述的思路，就可以考虑用高精度来改写以上算法了，但不管怎么说，核心还是不会变的。

首先是改预处理的部分，递推时直接使用高精度的加法，用一个二维数组记录就可以了。

其次是二分的部分，这部分应该不需要太大的改动，只需要注意两个参数第 $k$ 项斐波那契数和与其比较的数字。

最后就是比较的部分，按照字符串的比较方法，逐位进行比较即可！

Tips：

高精度加法与判断大小时需要考虑前导 $0$ 的影响
需要注意某一项斐波那契数就是 $a$ 或 $b$ 时对答案产生的影响
本题有多组测试数据，记得输出后对部分数据进行清空操作

代码

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
const int MAX = 550;
string a,b;
int lena[MAX],lenb[MAX],f[MAX][MAX],ans;
bool ok;
void pre ();
int work (int len[]);
int cmp (int len[],int x);
int main ()
{
    pre ();
    while (1)//多组数据
    {
        string a,b;
        cin>>a>>b;//字符串输入
        if (a == "0" && b == "0") break;
        memset (lena,0,sizeof (lena));
        memset (lenb,0,sizeof (lenb));
        ok = ans = 0;
        for (int i = 0;i < a.size ();++i) lena[a.size () - i] = a[i] - '0';
        for (int i = 0;i < b.size ();++i) lenb[b.size () - i] = b[i] - '0';
        int da = work (lena);
        if (ok) ans = 1;//特殊情况
        int db = work (lenb); 
        ans += db - da;
        cout<<ans<<endl;
    }
    return 0;
}
void pre ()//预处理部分
{
    f[1][1] = 1;f[2][1] = 2;
    for (int i = 3;i <= 500;++i)//高精度预处理出数列的每一项 
    {
        for(int j = 1;j <= 150;++j)
        {
            f[i][j] += f[i - 1][j] + f[i - 2][j];
            if (f[i][j] > 9)//进位处理 
            {
                f[i][j + 1] += f[i][j] / 10;
                f[i][j] %= 10; 
            }
        }
    }
}
int work (int len[])
{
    //找到与 len 最近的一项  
    int l = 1,r = 500;
    while (l <= r)//二分比较两者长度 
    {
        int mid = (l + r) >> 1;
        if (cmp (len,mid) == 0)//两数相等 
        {
            ok = 1;//len 就是这一项 
            return mid;
        } 
        else if (cmp (len,mid) == 1) r = mid - 1;//第 mid 项较大 
        else l = mid + 1;
    }
    return l - 1;
}
int cmp (int len[],int x)
{
    //0 1 2 分别表示相等，len 小，len 大
    int ka = 150,kb = 150;
    while (len[ka - 1] == 0) --ka;//前导 0
    while (f[x][kb - 1] == 0) --kb;
    if (ka < kb) return 1;
    else if (ka > kb) return 2;
    else
    {
        for (int i = ka;i >= 1;--i)
        {
            if (len[i] > f[x][i]) return 2;
            if (len[i] < f[x][i]) return 1;
        }
    }
    return 0;
}