C++大输入场景下无输出问题排查求助

核心问题拆解 #

• 输入格式不匹配：你的scanf("%lli,%i", &n , &m);要求输入用逗号分隔，但实际输入是空格分隔（比如9999999999999 2），导致n和m未被正确读取，后续逻辑全部失效。
• 栈溢出：int numbers[n];是C风格变长数组，分配在栈内存中。当n达到1e13这种极大值时，栈空间（通常仅几MB）完全无法容纳，直接触发栈溢出，程序静默崩溃。
• 无法完成的循环：n为1e13级别时，循环从2遍历到n根本不可能完成，哪怕每秒执行1e8次循环，也要耗费数年时间，必须用数学优化减少计算量。
• 整数溢出：计算numbers[i-1] + numbers[i-2]时，两个int类型值相加可能超过int的最大值（约2e9），导致溢出后数值错乱，取余结果完全错误。

修复方案 #

1. 修正输入格式 #

将scanf的格式符改为"%lld %d"（long long类型在scanf中通用格式符为%lld），匹配空格分隔的输入方式。

2. 抛弃数组，改用变量迭代 #

不需要存储整个斐波那契数列，只需保存前两个数值即可完成计算，彻底避免内存溢出问题。

3. 利用Pisano周期优化 #

斐波那契数列对m取余会呈现周期性（Pisano周期），只需计算n对该周期的余数k，再计算第k个斐波那契数对m取余即可，将1e13级别的计算量压缩到几百到几千次循环。

修正后的代码 #

#include <iostream>
using namespace std;

// 计算斐波那契取余的Pisano周期
long long pisano_period(long long m) {
    long long prev = 0;
    long long curr = 1;
    long long period = 0;
    while (true) {
        long long temp = curr;
        curr = (prev + curr) % m;
        prev = temp;
        period++;
        // 回到初始状态0,1时，周期结束
        if (prev == 0 && curr == 1) {
            return period;
        }
    }
}

// 计算第n个斐波那契数对m取余的结果
long long fib_mod(long long n, long long m) {
    if (n <= 1) {
        return n;
    }
    long long period = pisano_period(m);
    n = n % period;
    if (n == 0) {
        return 0;
    }
    long long prev = 0;
    long long curr = 1;
    for (long long i = 2; i <= n; i++) {
        long long temp = (prev + curr) % m;
        prev = curr;
        curr = temp;
    }
    return curr;
}

int main() {
    long long n;
    int m;
    // 匹配空格分隔的输入
    scanf("%lld %d", &n, &m);
    printf("%lld\n", fib_mod(n, m));
    return 0;
}

额外说明 #

• Pisano周期的最大长度为6*m，计算周期的循环会快速结束，即使m很大也不会有性能问题。
• 使用long long存储中间计算值，避免加法操作时的整数溢出。
• 代码全程无需数组，内存占用极低，可处理任意大小的n值。

内容的提问来源于stack exchange，提问作者Baris Karaer