[대수 클래스 + 재 부팅 연산 자 + 맵] HDU 1316 How many Fibs?

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[i] = '0';
    }
    void display ()
    {
        printf ("%s
", 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
", res); } return 0; }

좋은 웹페이지 즐겨찾기