c++ - 斐波纳契数的总和(仅可打印最后一位)

我一直在尝试解决有关找到大n斐波那契数列之和的最后一位数字的问题的解决方案。
我已经能够通过几个带有大n的测试用例。但是我被困在以下情况下，其中n =832564823476。我知道可以使用Pisano的周期来解决它，但是我无法给出有效的算法。任何帮助将是巨大的。谢谢。
我已实现的代码如下-

#include <iostream>
using namespace std;


int calc_fib(int n) {

    int fib[n+1];
    fib[0]=0;
    fib[1]=1;
    int res = 1;
    for(int i = 2; i<=n;i++){
        fib[i] = (fib[i-1]%10 + fib[i-2]%10)%10;
        res = res + fib[i];
    }
    return (res%10);
}

int main() {
    int n = 0;
    std::cin >> n;

    std::cout << calc_fib(n) << '\n';
    return 0;
}

最佳答案

解决了IT

适用于所有范围的输入。它适用于以下算法。
这个想法是要注意斐波纳契数的最后一位数字也出现在长度为60的序列中(来自先前的问题:因为pisano peiod 10为60)。无论n有多大，其最后一位都会出现在序列中的某个位置。
除了10的边缘情况(最后一位数字)以外，还有两件事。

第n个斐波纳契数列的总和= F(n + 2)-1

然后模块10的pisano周期=令n + 2 mod(60)= m然后找到F(m)mod(10)-1

代码如下；

#include <iostream>
using namespace std;

long long calc_fib(long long n) {

    n = (n+2)%60;
    int fib[n+1];
    fib[0]=0;
    fib[1]=1;
    int res = 1;
    for(int i = 2; i<=n;i++){
        fib[i] = (fib[i-1]%10 + fib[i-2]%10)%10;
        // res = res + fib[i];
    }
    // cout<<fib[n]<<"\n";
    if(fib[n] == 0){
        return 9;
    }
    return (fib[n]%10-1);
}

int main() {
    long long n = 0;
    std::cin >> n;

    std::cout << calc_fib(n) << '\n';
    return 0;
}

关于c++ - 斐波纳契数的总和(仅可打印最后一位)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38950579/