为何计算n=2816213588的斐波那契时抛出std::bad_alloc异常？

Let’s break down exactly why you’re hitting this error, and how to fix the core issues in your code:

First, the direct cause of the std::bad_alloc exception: your program is trying to allocate an impossibly large block of memory that your system can’t provide.

Let’s crunch the numbers: your code uses new int64_t[n] where n is 2816213588. An int64_t takes 8 bytes of memory, so this array would require:
2816213588 * 8 = 22529708704 bytes — that’s roughly 22 gigabytes of contiguous memory. Even if your system has enough total RAM, allocating a single contiguous block this size is almost never feasible (heap memory is fragmented, and operating systems impose strict limits on single allocations for user programs). The memory allocator simply can’t find a block that large, so it throws std::bad_alloc.

Beyond the memory failure, your code has a fundamental inefficiency: you don’t need to store the entire Fibonacci sequence in an array to compute the nth term. To calculate each Fibonacci number, you only need the previous two values — storing every term up to n is a massive waste of memory, especially for such an enormous n.

Making things even more unnecessary: your code already uses % 1000 to keep only the last three digits of each term. This is a perfect chance to leverage the Pisano period: Fibonacci numbers modulo any positive integer m repeat in a predictable cycle. For m=1000, the Pisano period is 1500 — meaning instead of computing 2.8 billion terms, you only need to compute up to 1500 after reducing n to fit within the cycle.

Here’s a revised, optimized version of your code that fixes both the memory issue and the efficiency problem:

#include <iostream>
#include <cstdint>
using namespace std;

// Basic iterative Fibonacci with modulo, no array needed
int64_t fibonacci(int64_t n, int64_t m) {
    if (n <= 1) return n;
    int64_t prev_prev = 0; // F(0)
    int64_t prev = 1;      // F(1)
    int64_t current;
    for (int64_t i = 2; i <= n; ++i) {
        current = (prev_prev + prev) % m;
        prev_prev = prev;
        prev = current;
    }
    return prev % m;
}

// Calculate Pisano period for modulo m
int64_t pisano_period(int64_t m) {
    int64_t prev = 0;
    int64_t curr = 1;
    int64_t period = 0;
    while (true) {
        int64_t temp = (prev + curr) % m;
        prev = curr;
        curr = temp;
        period++;
        if (prev == 0 && curr == 1) {
            return period;
        }
    }
}

// Optimized version for extremely large n using Pisano period
int64_t optimized_fibonacci(int64_t n, int64_t m) {
    if (m == 1) return 0;
    int64_t period = pisano_period(m);
    n = n % period;
    return fibonacci(n, m);
}

int main() {
    int64_t n=0, m=0;
    cin>>n>>m;
    // Use the optimized function for huge values of n
    cout<<optimized_fibonacci(n+1, m);
    return 0;
}

Key improvements in this code:

• Eliminates large array allocations entirely, using only 3 variables to track the last two Fibonacci terms.
• Leverages the Pisano period to reduce the number of iterations drastically — for m=1000, it cuts 2.8 billion iterations down to just 1500 at most.

内容的提问来源于stack exchange，提问作者yash jain