时间戳

首页 > 解决方案 > 如何找到大数的斐波那契和？

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

问题描述

我正在解决一个 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)错误并且不返回任何内容。请帮助我理解这里的问题以及如何处理它。任何其他建议也将不胜感激。

标签： c++c++11

解决方案

在进行模块化添加时，您需要将您的 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]会导致溢出。

在此处阅读有关模运算的更多信息。

推荐阅读