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)，你可以在我到达病房时将结果收集到一个单独的变量中。这样，您可以避免 calc_fib(a-1);

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

你正在做

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

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

查找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;
}

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

Last Digit of the Sum of Fibonacci Numbers in range a to b

c++

algorithm

fibonacci