c++ - 如何找到大数的斐波那契和？

Question

这个问题在这里已经有了答案:





initialize array with stackoverflow error [duplicate]

(2 个回答)



Finding out nth fibonacci number for very large 'n'

(23 个回答)



Finding the fibonacci number of large number

(1 个回答)


1年前关闭。




我正在解决一个 CSES 问题，其中我必须找到第一个“n”斐波那契数的总和。编码:

#pragma GCC optimize("Ofast")
#include <iostream>
 
using namespace std;
 
int main()
{
    unsigned long long int n;
    scanf("%llu", &n);
    unsigned long long int seq[n];
    seq[0] = 0;
    seq[1] = 1;
    unsigned long long int mod = 1000000000 + 7;
    for (unsigned long long int i = 2; i < n + 1; i++) {
        seq[i] = (seq[i - 1] + seq[i - 2]) % mod;
    }
    cout << seq[n];
}

问题指定 n 的值可以达到 10^18，因此我使用了 unsigned long long int 初始化 n。该问题还指示给出模 7 的答案。该代码对于 n 最多 4 位的值可以正常工作，但是当 n 的值上升到 10^18 的上限时会中断。它给出 (0xC00000FD)错误并且不返回任何内容。请帮助我理解这里的问题以及如何处理它。任何其他建议也将不胜感激。

Answer 1

在进行模块化添加时，您需要将您的 mod 应用于您添加的每个值。
例如，(a + b) % c = (a % c + b % c) % c。
这意味着在您的代码中:

seq[i] = (seq[i - 1] % mod + seq[i - 2] % mod) % mod;

否则，添加 seq[i - 1]和 seq[i - 2]将导致溢出。
阅读有关模算术的更多信息 here .