HDU 1316 How Many Fibs

題意：給出a，b；求區間[a,b]內有多少個斐波那契數，其中a <= b <= 10^100

暫時我這個大數類只重載了加號，等於號，大於等於，小於等於

C++代碼 
#include <iostream> 
#include <fstream> 
#include <algorithm> 
#include <string> 
#include <set> 
//#include <map> 
#include <queue> 
#include <utility> 
#include <iomanip> 
#include <stack> 
#include <list> 
#include <vector> 
#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
#include <cmath> 
#include <ctime> 
#include <ctype.h> 
using namespace std; 
//VC6貌似要#include <iostream.h>，而且using namespace std要注釋掉; 
class BigInteger{ 
public: 
    BigInteger () 
    { 
        for (int i = 0; i < 2010; i++) 
            str[i] = '0'; 
    } 
    void display () 
    { 
        printf ("%s\n", str); 
    } 
    char * operator = (char *s) 
    { 
        strcpy (str, s); 
        len = strlen (s); 
        return s; 
    } 
    friend BigInteger operator + (BigInteger &a, BigInteger &b); 
    friend bool operator >= (BigInteger &a, BigInteger &b); 
    friend bool operator <= (BigInteger &a, BigInteger &b); 
    char str[2010];    //一個大數的表示方式，對於這題，定得太大了…… 
    int len;    //一個大數的長度，即位數 
}; 
 
BigInteger operator + (BigInteger &a, BigInteger &b) 
{ 
    BigInteger tp, ta, tb, res; 
    int k = a.len > b.len ? a.len : b.len, w = 0, i; 
    //翻轉 
    for (i = a.len - 1; i >= 0; i--) 
        ta.str[w++] = a.str[i]; 
    ta.str[w] = 0; 
    w = 0; 
    for (i = b.len - 1; i >= 0; i--) 
        tb.str[w++] = b.str[i]; 
    tb.str[w] = 0; 
    w = 0; 
    //按位相加 
    for (i = 0; i < k; i++) 
    { 
        if (ta.str[i] == 0) 
            ta.str[i] = '0'; 
        if (tb.str[i] == 0) 
            tb.str[i] = '0'; 
        tp.str[i] = ((ta.str[i]-'0') + (tb.str[i]-'0') + w) + '0'; 
        w = 0; 
        if (tp.str[i] > '9') 
            tp.str[i] -= 10, w = 1; 
    } 
    if (w > 0) 
        tp.str[k]++, k++; 
    w = 0; 
    for (i = k - 1; i >= 0; i--) 
        res.str[w++] = tp.str[i]; 
    res.str[w] = 0; 
    res.len = k; 
    return res; 
} 
 
bool operator >= (BigInteger &a, BigInteger &b) 
{ 
    if (a.len > b.len) 
        return true; 
    if (a.len == b.len && strcmp (a.str, b.str) >= 0) 
        return true; 
    return false; 
} 
 
bool operator <= (BigInteger &a, BigInteger &b) 
{ 
    if (a.len < b.len) 
        return true; 
    if (a.len == b.len && strcmp (a.str, b.str) <= 0) 
        return true; 
    return false; 
} 
 
BigInteger f[500], a, b; 
 
int main() 
{ 
    int i, map[110], start, end, res; 
    char s[105], p[105]; 
    f[1] = "1"; 
    f[2] = "2"; 
    map[1] = 1; 
    for (i = 3; i < 500; i++) 
    { 
        f[i] = f[i-1] + f[i-2]; 
        if (f[i].len == f[i-1].len) 
            map[f[i].len] = map[f[i-1].len];    //長度映射到位置 
        else map[f[i].len] = i; 
    } 
    while (scanf ("%s%s", s, p)) 
    { 
        if (!strcmp (s, "0") && !strcmp (p, "0")) 
            break; 
        a = s, b = p; 
        start = map[a.len];   //根據a、b的位數讀取范圍 
        end = map[b.len+1]; 
        res = 0; 
        for (i = start; i <= end; i++)//i是位置，相當於f[i]的i，是下標，范圍只有500 
            if (f[i] >= a && f[i] <= b) 
                res++; 
        printf ("%d\n", res); 
    } 
    return 0; 
}