HDU 1316 How Many Fibs：大整數斐波那契區間計數解法詳解

編輯：關於C語言

題目大意

給定兩個大整數 a, b (a ≤ b ≤ 10^100)，求閉區間 [a, b] 內有多少個斐波那契數。輸入以 0 0 結束。

核心挑戰

斐波那契數增長極快，F(500) 已超過 10^100，故只需預計算前 500 項。
數值超出 64 位整數範圍，必須實現大整數加法與比較。

大整數類設計 (BigInteger)

採用字元陣列存儲十進制數字，低位在前 (反序) 便於逐位運算。

class BigInteger {
public:
    char str[2010]; // 足夠存 10^100
    int len;        // 有效位數

    BigInteger() { memset(str, '0', sizeof(str)); len = 0; }
    void display() { printf("%s\n", str); }

    // 賦值：字串 -> BigInteger
    char* operator=(char* s) {
        strcpy(str, s);
        len = strlen(s);
        return s;
    }

    friend BigInteger operator+(BigInteger&, BigInteger&);
    friend bool operator>=(BigInteger&, BigInteger&);
    friend bool operator<=(BigInteger&, BigInteger&);
};

大整數加法實現

BigInteger operator+(BigInteger& a, BigInteger& b) {
    BigInteger ta, tb, tp, res;
    // 反轉存入 ta、tb (低位在索引 0)
    for (int i = a.len-1, w=0; i>=0; --i) ta.str[w++] = a.str[i];
    ta.str[w] = 0;
    for (int i = b.len-1, w=0; i>=0; --i) tb.str[w++] = b.str[i];
    tb.str[w] = 0;

    int k = max(a.len, b.len), w = 0;
    for (int i = 0; i < k; ++i) {
        char ca = ta.str[i] ? ta.str[i] : '0';
        char cb = tb.str[i] ? tb.str[i] : '0';
        tp.str[i] = (ca-'0') + (cb-'0') + w + '0';
        w = 0;
        if (tp.str[i] > '9') { tp.str[i] -= 10; w = 1; }
    }
    if (w) tp.str[k++] = '1';
    // 反轉回 res
    for (int i = k-1, w=0; 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;
}

預計算與長度映射優化

斐波那契數位數單調遞增。建立 map[len] = 首個達到該位數的斐波那契索引，查詢時只需比對位數範圍內的極少數項。

BigInteger f[500];
int map[110]; // map[位數] = 索引

f[1] = "1"; f[2] = "2"; map[1] = 1;
for (int 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) == 2) {
    if (strcmp(s, "0")==0 && strcmp(p, "0")==0) break;
    a = s; b = p;
    int start = map[a.len];
    int end   = map[b.len + 1]; // 稍大一位確保覆蓋
    int cnt = 0;
    for (int i = start; i <= end; ++i)
        if (f[i] >= a && f[i] <= b) ++cnt;
    printf("%d\n", cnt);
}

完整代碼 (G++ 可直接編譯)

#include 
using namespace std;

struct BigInteger {
    string s;
    BigInteger() {}
    BigInteger(const string& str) : s(str) {}
    BigInteger& operator=(const string& str) { s = str; return *this; }
    friend BigInteger operator+(const BigInteger& a, const BigInteger& b) {
        string res; int ca = 0;
        for (int i = 0; i < max(a.s.size(), b.s.size()) || ca; ++i) {
            int da = i < a.s.size() ? a.s[a.s.size()-1-i]-'0' : 0;
            int db = i < b.s.size() ? b.s[b.s.size()-1-i]-'0' : 0;
            int sum = da + db + ca;
            res.push_back('0' + sum%10); ca = sum/10;
        }
        reverse(res.begin(), res.end());
        return BigInteger(res);
    }
    friend bool operator>=(const BigInteger& a, const BigInteger& b) {
        if (a.s.size() != b.s.size()) return a.s.size() > b.s.size();
        return a.s >= b.s;
    }
    friend bool operator<=(const BigInteger& a, const BigInteger& b) {
        if (a.s.size() != b.s.size()) return a.s.size() < b.s.size();
        return a.s <= b.s;
    }
    int len() const { return s.size(); }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    vector f(500);
    vector mp(110, -1);
    f[1] = "1"; f[2] = "2"; mp[1] = 1;
    for (int i = 3; i < 500; ++i) {
        f[i] = f[i-1] + f[i-2];
        if (f[i].len() == f[i-1].len()) mp[f[i].len()] = mp[f[i-1].len()];
        else mp[f[i].len()] = i;
    }
    string a, b;
    while (cin >> a >> b) {
        if (a=="0" && b=="0") break;
        int st = mp[a.size()];
        int ed = mp[b.size()+1];
        int cnt = 0;
        for (int i = st; i <= ed; ++i)
            if (f[i] >= a && f[i] <= b) ++cnt;
        cout << cnt << '\n';
    }
    return 0;
}