【大数类+重载运算符+映射】HDU 1316 How Many Fibs?

基德KID.1412

http://acm.hdu.edu.cn/showproblem.php?pid=1316

题意：给出a，b；求区间[a,b]内有多少个斐波那契数，其中a <= b <= 10^100

暂时我这个大数类只重载了加号，等于号，大于等于，小于等于


#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 = '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;    ta.str[w] = 0;    w = 0;    for (i = b.len - 1; i >= 0; i--)        tb.str[w++] = b.str;    tb.str[w] = 0;    w = 0;    //按位相加    for (i = 0; i < k; i++)    {        if (ta.str == 0)            ta.str = '0';        if (tb.str == 0)            tb.str = '0';        tp.str = ((ta.str-'0') + (tb.str-'0') + w) + '0';        w = 0;        if (tp.str > '9')            tp.str -= 10, w = 1;    }    if (w > 0)        tp.str[k]++, k++;    w = 0;    for (i = k - 1; i >= 0; i--)        res.str[w++] = tp.str;    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 = f[i-1] + f[i-2];if (f.len == f[i-1].len)map[f.len] = map[f[i-1].len];    //长度映射到位置else map[f.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，是下标，范围只有500if (f >= a && f <= b)res++;printf ("%d\n", res);}    return 0;}