【大数类+重载运算符+映射】HDU 1316 How Many Fibs?
http://acm.hdu.edu.cn/showproblem.php?pid=1316题意：给出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; //一个大数的表示方式，对于这题，定得太大了…… 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 = a.str; ta.str = 0; w = 0; for (i = b.len - 1; i >= 0; i--) tb.str = b.str; tb.str = 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++; w = 0; for (i = k - 1; i >= 0; i--) res.str = tp.str; res.str = 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, a, b;int main(){ int i, map, start, end, res;char s, p; f = "1";f = "2";map = 1; for (i = 3; i < 500; i++){f = f + f;if (f.len == f.len)map.len] = map.len]; //长度映射到位置else map.len] = i;} while (scanf ("%s%s", s, p)){if (!strcmp (s, "0") && !strcmp (p, "0"))break;a = s, b = p;start = map; //根据a、b的位数读取范围end = map;res = 0;for (i = start; i <= end; i++)//i是位置，相当于f的i，是下标，范围只有500if (f >= a && f <= b)res++;printf ("%d\n", res);} return 0;}
页:
[1]