大数的斐波那契和（仅打印最后一位）

Question

我一直在尝试找到一个解决方案来解决寻找大 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;
}

原文由 codeyourstack 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

解决了

适用于所有输入范围。它适用于以下算法。这个想法是要注意斐波那契数的最后一位数字也出现在长度为 60 的序列中（来自上一个问题：因为 10 的 pisano peiod 是 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;
}

原文由 codeyourstack 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

如果您只需要按您所说的输出最后一位，我认为您可以使用您提到的 Pisano Period ，对于模10，循环长度只有60，您可以预先制作一个60的数组位数。

如果您想自己计算，我认为您可以使用 Matrix Exponentiation 它为您提供 O(lg N) 复杂性，在计算矩阵指数时，请继续存储临时结果模 10。请参阅 矩阵 部分以供参考。

原文由 shole 发布，翻译遵循 CC BY-SA 3.0 许可协议