Fibonacci大数和（仅打印最后一位数字）

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

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

Answer 2

如果你只需要按照你的说法输出最后一位数字，我想你可以使用你提到的Pisano Period，对于模块化10，循环长度只有60，你可以预先制作一个60位的数组。

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

Answer 3

为您的功能删除阵列。

#include "stdafx.h"
#include <iostream>
using namespace std;
int calc_fib(long long int n) {

    int fibzero = 0;
    int fibone = 1;
    int fibnext;
    long long int res = 1;
    for (long long int i = 2; i <= n; i++) {

        fibnext = (fibone + fibzero) % 10;
        fibzero = fibone;
        fibone = fibnext;
        res = res + fibnext;
    }
    return (res % 10);
}

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

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

Answer 4

实际上它比Niall回答更容易

int get_fibonacci_sum_last_digit(long long n) {
    const int kPisanoSize = 60;
    int rest = n % kPisanoSize;
    int preparedNumbers[kPisanoSize] = {0, 1, 2, 4, 7, 2, 0, 3, 4, 8, 3, 
        2, 6, 9, 6, 6, 3, 0, 4, 5, 0, 6, 7, 4, 2, 7, 0, 8, 9, 8, 8, 7, 
        6, 4, 1, 6, 8, 5, 4, 0, 5, 6, 2, 9, 2, 2, 5, 8, 4, 3, 8, 2, 1, 
        4, 6, 1, 8, 0, 9, 0};
    return preparedNumbers[rest];

}