費波那契數列模運算：O(n) 迭代法求 F(n) mod 10007

問題描述

給定 n (1 ≤ n ≤ 1,000,000)，計算費波那契數 F(n) 模 10007 的餘數。
遞推：F(1)=F(2)=1，F(n)=F(n-1)+F(n-2)。
直接計算 F(n) 會溢位（指數級增長），利用模運算性質：(a+b) mod m = ((a mod m) + (b mod m)) mod m，每步取模即可。

演算法：滾動陣列迭代 O(n) 時間、O(1) 空間

#include <stdio.h>

int fib_mod(int n, int mod) {
    if(n <= 2) return 1 % mod;
    int a = 1, b = 1, c;
    for(int i = 3; i <= n; i++) {
        c = a + b;
        if(c >= mod) c %= mod;  // 或直接 c %= mod
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", fib_mod(n, 10007));
    return 0;
}

關鍵優化點

• **只保留最近兩項**：滾動變數 a, b，空間 O(1)
• **每步取模**：防止整數溢位，int 足夠 (10007² < 2³¹)
• **快速輸入**：大量測試案例可用 fastio 或 scanf 足夠

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

利用矩陣形式：

[ F(n)   ]   = [1 1]^(n-1)  [F(1)]
[ F(n-1) ]     [1 0]         [F(0)]

矩陣快速冪可在 O(log n) 計算，適合 n > 10⁹ 場景。對 n ≤ 10⁶，O(n) 迭代已足夠快 (約 0.01s)。

皮薩諾週期優化（理論）

模 m 的費波那契數列週期稱皮薩諾週期 π(m)。對 m=10007 (質數)，π(m) 整除 m-1 或 2(m+1)。預計算週期可 O(1) 回答多次查詢，但預計算本身 O(π(m)) 可能更慢。

測試驗證

常見錯誤

• 未對 n=1,2 特判，迴圈從 3 開始
• 用遞歸導致棧溢位與重複計算
• 未取模導致整數溢位 (n=50 即超過 64 位)
• 模數寫死，缺乏通用性

總結

費波那契模運算是動態規劃與數論結合的經典入門題。「滾動陣列 + 每步取模」是標準解法，掌握後可擴展至線性遞推數列、矩陣快速冪、皮薩諾週期等進階主題。