C++中计算超186项斐波那契数末位的标准库实现问题

首先，你不需要自定义大整数类型，因为我们只需要斐波那契数的最后一位数字，可以利用模运算的性质大幅简化计算：

两个数之和的最后一位，等于这两个数最后一位之和的最后一位，即 (a + b) % 10 = [(a % 10) + (b % 10)] % 10

基于这个性质，我们完全不需要存储完整的斐波那契数，只需要跟踪每一项的最后一位即可，这样用普通的int类型就足够，永远不会溢出。

优化后的基础代码 #

int get_fibonacci_last_digit_fast(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    int prev_prev = 0; // f[0]的最后一位
    int prev = 1;      // f[1]的最后一位
    int current;
    
    for (int i = 2; i <= n; ++i) {
        current = (prev_prev + prev) % 10;
        prev_prev = prev;
        prev = current;
    }
    
    return current;
}

进一步优化：利用周期规律 #

斐波那契数的最后一位存在周期性（称为皮萨诺周期，模10时周期为60）。也就是说，第n项的最后一位和第n+60项的最后一位完全相同。如果n很大，我们可以先计算n % 60，再用上面的方法计算，大幅减少循环次数：

int get_fibonacci_last_digit_fast(int n) {
    n = n % 60; // 模10的皮萨诺周期是60
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    int prev_prev = 0;
    int prev = 1;
    int current;
    
    for (int i = 2; i <= n; ++i) {
        current = (prev_prev + prev) % 10;
        prev_prev = prev;
        prev = current;
    }
    
    return current;
}

关于自定义大整数的补充（非当前需求必要） #

如果后续需求扩展到需要完整的大斐波那契数，而非仅最后一位，可以用标准库实现自定义大整数：

• 用std::vector<int>存储每一位数字（建议从低位到高位存储，方便加法进位处理）
• 实现大整数加法：逐位相加并处理进位

示例代码（仅作演示，针对当前问题无需使用）：

#include <vector>
#include <algorithm>

std::vector<int> add_big_numbers(const std::vector<int>& a, const std::vector<int>& b) {
    std::vector<int> result;
    int carry = 0;
    int max_len = std::max(a.size(), b.size());
    
    for (int i = 0; i < max_len || carry; ++i) {
        if (i < a.size()) carry += a[i];
        if (i < b.size()) carry += b[i];
        result.push_back(carry % 10);
        carry /= 10;
    }
    
    return result;
}

// 获取第n项斐波那契数的完整大整数
std::vector<int> get_fibonacci_big(int n) {
    if (n == 0) return {0};
    if (n == 1) return {1};
    
    std::vector<int> prev_prev = {0};
    std::vector<int> prev = {1};
    std::vector<int> current;
    
    for (int i = 2; i <= n; ++i) {
        current = add_big_numbers(prev_prev, prev);
        prev_prev = prev;
        prev = current;
    }
    
    // 反转得到高位在前的顺序（可选）
    std::reverse(current.begin(), current.end());
    return current;
}

但再次强调，针对你当前只需要最后一位的需求，前两种方法已经足够高效且简洁，完全不需要自定义大整数。

内容的提问来源于stack exchange，提问作者Dwayne St George