藍橋杯 C 語言題：斐波那契數列模 10007 求解

題目背景

給定斐波那契數列遞推公式：Fn = Fn-1 + Fn-2，其中 F1 = F2 = 1。當 n 較大時，Fn 數值極大，要求輸出 Fn % 10007 的結果。輸入範圍：1 ≤ n ≤ 1,000,000。

核心思路

直接計算 Fn 會導致溢出，且效率低下。利用模運算性質：(a + b) % m = (a % m + b % m) % m，可在遞推過程中直接取模，僅保留餘數，避免大數運算。

常見錯誤與修正

初學者常犯的錯誤是迴圈起始索引與賦值順序錯誤。以下是修正後的關鍵代碼片段：

#include <stdio.h>
#define M 10007
int main() {
    long n, i;
    int a1 = 1, a2 = 1, sum = 0, t;
    scanf("%ld", &n);
    if (n == 1 || n == 2) { printf("1\n"); return 0; }
    for (i = 3; i <= n; i++) {
        t = a2;
        a2 = (a1 + a2) % M;
        a1 = t;
    }
    printf("%d\n", a2 % M);
    return 0;
}

關鍵修正點：

• 迴圈從 i = 3 開始，因前兩項已知。
• 使用暫存變量 t 保存 a2 舊值，正確更新 a1、a2。
• 最終輸出 a2 而非 sum，避免多一次取模運算。

複雜度分析

時間複雜度 O(n)，空間複雜度 O(1)，完全滿足 n ≤ 1,000,000 的要求。