c++ - a到b范围内斐波那契数之和的最后一位

Question

我的解决方案在输出中的测试用例 1234 12345 失败，它给出了输出 2 而不是正确的输出 8，尽管问题样本中的一些测试用例已经通过。请指出我的错误。谢谢你。

#include <bits/stdc++.h>

using namespace std;

int calc_fib(long long n) {
    long long int m, o = 0, p = 1, q = 1;
    m = (n+2) % 60;

    for(long long int i = 2 ; i <= m ; i++) {
        q = o + p;
        o = p;
        p = q;
    }

    //if m=0 then q should be 0 and not 1 so base case
    if(m == 0) q = 0;

    return q;
}

int main() {
    long long a, b;
    cin>>a>>b;

    int result1 = calc_fib(b);
    int result2 = calc_fib(a-1);
    int final_result = ((result1%10) - (result2%10) + 10) % 10;

    cout<<final_result;
    return 0;
}

Answer 1

如果您仍然这样做calc_fib(b)，您可以在我到达 a 和病房时将结果收集到一个单独的变量中。这样，您可以避免calc_fib(a-1)；

a如果这是针对to的单个范围b，则可以即时计算，否则通过将它们缓存在数组中来预先计算它们，然后执行calc_fib(b) - calc_fib(a-1).

你在做

    q = o + p;
    o = p;
    p = q;

这将导致整数溢出，因为斐波那契数在 20^次左右之后会变大。

查找last digit of sum of all fibonacci from a to b 等价于 just sum all last digits of each fibonacci from ath term to bth term。所以，你可以继续修改它10，无论是总和还是数字。

#include <bits/stdc++.h> // use any other alternative for this as it doesn't seem to be a good practice

using namespace std;

int calc_fib(long long a,long long b) {
    if(b <= 2) return b;
    int prev = 1,curr = 1,sum = a < 3 ? 2 : 0;
    long long int i = 1;
    for(i = 3; i <= b; ++i){
        curr += prev;
        prev = curr - prev;
        if(i >= a){
            sum = (sum + curr) % 10;
        }       
        prev %= 10;
        curr %= 10;
    }

    return sum;
}

int main() {
    long long a = 0, b = 0;
    cin>>a>>b;
    cout<<calc_fib(a,b);
    return 0;
}