hdu 1316 How Many Fibs?

点击即可传送到1316

              **How Many Fibs?**
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5366    Accepted Submission(s): 2088



Problem Description

Recall the definition of the Fibonacci numbers: 
f1 := 1 
f2 := 2 
fn := fn-1 + fn-2 (n >= 3) 

Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a, b]. 





Input

The input contains several test cases. Each test case consists of two non-negative integer numbers a and b. Input is terminated by a = b = 0. Otherwise, a <= b <= 10^100. The numbers a and b are given with no superfluous leading zeros.





Output

For each test case output on a single line the number of Fibonacci numbers fi with a <= fi <= b. 





Sample Input

10 100
1234567890 9876543210
0 0





Sample Output

5
4

题目大意：给你两个数a和b，求a和b之间有几个斐波那契数，包括a和b

解题思路：因为本题是一个很大的数，所以就用字符串，然后再加一个二分就好了。。。。
请看代码：

/*
2015 - 8 - 13 下午
Author: ITAK
今日的我要超越昨日的我，明日的我要胜过今日的我，
以创作出更好的代码为目标，不断地超越自己。
*/
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 105;
char data[1000][N+2];
char a[N+2],b[N+2];
int cmp(char *s1, char *s2)
{
    for(int i=0; i<=N; i++)
    {
        if(i == N)
            return s1[i] - s2[i];
        if(s1[i] != s2[i])
            return s1[i] - s2[i];
    }
}

int Find_up(int i, char *x)
{
    int low=0, high=i;
    while(low <= high)
    {
        int mid = (high+low)/2;
        int val = cmp(x, data[mid]);
        if(val > 0)
            low = mid + 1;
        if(val == 0)
            return mid - 1;
        if(val < 0)
            high = mid - 1;
    }
    return high;
}

int Find_down(int i, char *x)
{
    int low=0, high=i;
    while(low <= high)
    {
        int mid = (high+low)/2;
        int val = cmp(x, data[mid]);
        if(val > 0)
            low = mid + 1;
        if(val == 0)
            return mid + 1;
        if(val < 0)
            high = mid - 1;
    }
    return low;
}
int main()
{
    data[0][105] = 1;
    data[1][105] = 2;
    int i = 2;
    int p = 105;
    while(data[i-1][5] <= 1)
    {
        for(int j=105; j>=p; j--)
            data[i][j] = data[i-1][j] + data[i-2][j];
        for(int j=105; j>=p; j--)
        {
            int c = data[i][j]/10;
            if(c > 0)
            {
                data[i][j] %= 10;
                data[i][j-1] += c;
            }
        }
        if(data[i][p-1] > 0)
            p--;
        i++;
    }
    while(~scanf("%s%s",a,b))
    {
        if(a[0]=='0' && b[0]=='0')
            break;
        int lena = strlen(a)-1;
        int lenb = strlen(b)-1;
        int k;
        for(int d=lena,k=N; d>=0; d--,k--)
        {
            a[k] = a[d] - '0';
            a[d] = 0;
        }
        for(int d=lenb,k=N; d>=0; d--,k--)
        {
            b[k] = b[d] - '0';
            b[d] = 0;
        }
        int L = Find_up(i-1, a);
        int R = Find_down(i-1, b);
        printf("%d\n",R-L-1);
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
    }
    return 0;
}