C 語言藍橋杯題：斐波那契數列模 10007 邊界條件修正

題目要求

計算斐波那契數列第 n 項模 10007 的餘數。
F1 = 1, F2 = 1, Fn = Fn-1 + Fn-2 (n > 2)
輸入 1 <= n <= 1,000,000，輸出 Fn % 10007。

原代碼錯誤

for (i = 1; i <= n; i++) {
    sum = a1 % M;
    t = a2;
    a2 = (a1 + a2) % M;
    a1 = t;
}
printf("%d\n", sum);

• 循環從 1 開始，實際 F1, F2 已知，應從 3 開始迭代。
• sum 更新邏輯錯誤，最終輸出非 Fn。
• 未處理 n=1, n=2 邊界情況。

修正代碼

#include 
#define M 10007

int main() {
    long n;
    scanf("%ld", &n);
    
    if (n <= 2) { // F1=1, F2=1
        printf("1\n");
        return 0;
    }
    
    int a1 = 1, a2 = 1, t;
    for (long i = 3; i <= n; i++) { // 從第3項開始
        t = a2;
        a2 = (a1 + a2) % M; // a2 存儲 Fi
        a1 = t;             // a1 存儲 Fi-1
    }
    printf("%d\n", a2); // 循環結束 a2 即為 Fn % M
    return 0;
}

關鍵點

1. 邊界處理：n=1,2 直接返回 1。
2. 循環起點：i=3，因前兩項已知。
3. 滾動變量：a1, a2 交替保存前兩項，空間 O(1)。
4. 取模優化：每步取模防止溢出，利用 (a+b)%M = (a%M + b%M)%M。
5. 類型選擇：n 用 long，循環變量 i 同理。

進階：矩陣快速冪 O(log n)

對於極大 n（如 10^18），可用矩陣快速冪：

[Fn  ]   = [1 1]^(n-1) * [F1]
[Fn-1]     [1 0]          [F0]

但本題 n <= 1e6，線性遞推完全足夠（約 1ms）。