斐波那契数列m到n项和的末位求解及代码排查求助

我来帮你分析代码里的问题，以及适配超大数值场景的优化思路：

核心问题分析 #

你的代码方向是对的（利用斐波那契末位的Pisano周期60处理超大n），但两个关键问题导致测试用例失败：

1. 未处理减法后的负数情况
   公式calc_fib(n) - calc_fib(m-1)的逻辑是对的（从m到n的和 = 前n项和 - 前m-1项和），但当calc_fib(n)的末位小于calc_fib(m-1)的末位时，差值会是负数（比如测试用例1中，前10项和末位是3，前4项和末位是7，3-7=-4）。我们需要的是末位正数，这时候应该把结果加10再取模10，才能得到正确的6。

2. 变长数组的非标准使用
   你用了int fib[n+1];，这是C语言的变长数组特性，在C++中属于非标准扩展，虽然部分编译器支持，但不够稳妥。而且因为mod10的Pisano周期是60，我们最多只需要61个元素的数组，完全可以用固定大小的数组替代。

另外，虽然你的代码在m=0时（m-1=-1）刚好能得到正确结果，但显式处理k<0的情况会让逻辑更清晰。

修正后的可运行代码 #

先修复上述问题，得到能通过所有测试用例的代码：

#include <iostream>
using namespace std;

int calc_fib_sum_last_digit(long long k) {
    if (k < 0) {
        return 0; // 前-1项和为0（无元素相加）
    }
    // 前k项和 = F(k+2) - 1，取末位
    long long idx = (k + 2) % 60; // Pisano周期mod10为60
    // 用固定大小数组，避免非标准变长数组问题
    int fib[61];
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= idx; ++i) {
        fib[i] = (fib[i-1] + fib[i-2]) % 10;
    }
    int result = fib[idx] - 1;
    return result < 0 ? 9 : result % 10; // 处理fib[idx]为0的情况（0-1=-1，末位为9）
}

int main() {
    long long m, n;
    cin >> m >> n;
    int sum_n = calc_fib_sum_last_digit(n);
    int sum_m_1 = calc_fib_sum_last_digit(m-1);
    // 处理负数差值，加10再取模确保结果为正
    int final_result = (sum_n - sum_m_1 + 10) % 10;
    cout << final_result << endl;
    return 0;
}

测试用例1输入5 10会输出正确的6；测试用例2输入1 10000000输出5，和预期一致。

更优实现（空间优化版） #

上面的代码已经能处理任意超大数值，我们还可以进一步优化空间，不需要数组，只用两个变量迭代计算F(k+2)的末位：

#include <iostream>
using namespace std;

int calc_fib_sum_last_digit(long long k) {
    if (k < 0) {
        return 0;
    }
    long long idx = (k + 2) % 60;
    if (idx == 0) {
        return 9; // F(60)末位为0，0-1=-1，末位为9
    }
    int a = 0, b = 1;
    for (int i = 2; i <= idx; ++i) {
        int c = (a + b) % 10;
        a = b;
        b = c;
    }
    int result = b - 1;
    return result < 0 ? 9 : result;
}

int main() {
    long long m, n;
    cin >> m >> n;
    int sum_n = calc_fib_sum_last_digit(n);
    int sum_m_1 = calc_fib_sum_last_digit(m-1);
    cout << (sum_n - sum_m_1 + 10) % 10 << endl;
    return 0;
}

这个版本用O(1)的空间，计算量仅为最多60次迭代，完美适配n=82364572389这类超大数值场景。

关键逻辑说明 #

1. Pisano周期的利用：斐波那契数列的末位数字每60项重复一次（Pisano周期mod10=60），所以任何大的k都可以先取模60，把计算量降到常数级别。

2. 和的公式：从索引m到n的和 = 前n项和 - 前m-1项和，而前k项和的公式是F(k+2) - 1（其中F(0)=0，F(1)=1），只需计算F(n+2)和F(m+1)的末位代入即可。

3. 负数处理：无论是计算F(k+2)-1还是最终的差值，只要结果为负，加10再取模10就能得到正确的末位正数。

内容的提问来源于stack exchange，提问作者Kushal Dev