ACM 費波納契取模 520：利用模運算性質避免溢位與超時

題目：f(n) = f(n-1) + f(n-2), f(1)=f(2)=1，求 f(n) % 520，n ≤ 1e9，多組測資。

核心觀察

模運算具分配律：(a+b) % m = (a%m + b%m) % m。因此可在每一步取模，**數值永不超過 520**，完全避免溢位。

線性遞推 (O(n)) 會超時

n = 1e9 太大，需用 **矩陣快速冪 (O(log n))** 或 **皮薩諾週期** 加速。

皮薩諾週期法

• 模 m 的費波納契數列週期 ≤ 6m。對 m=520，週期 ≤ 3120。
• 預先計算前 3120 項模值存陣列，查詢時直接取 arr[n % period]。

參考程式碼

int period = 0;
int[] mod = new int[10000];
mod[1] = mod[2] = 1;
for (int i = 3; ; i++) {
    mod[i] = (mod[i-1] + mod[i-2]) % 520;
    if (mod[i-1] == 1 && mod[i] == 1) { period = i-2; break; }
}
// 查詢
while (sc.hasNextLong()) {
    long n = sc.nextLong();
    System.out.println(mod[(int)(n % period)]);
}

預計算週期後，單次查詢 O(1)，輕鬆通過大數據測試。