主題

ZeroJudge - d271: 11582 - Colossal Fibonacci Numbers! 解題心得

Not In My Back Yard | 2021-05-05 00:00:08 | 巴幣 0 | 人氣 66

題目連結:


題目大意:
已知費氏數列 f 為以下定義:
f(0) = 0
f(1) = 1
f(i+2) = f(i+1) + f(i) 對於 i ≧ 0

輸入第一列給定一正整數 t (t ≦ 10000),代表有 t 筆測試資料,每筆佔一列。

每列給定三整數 a 、 b 、 n (0 ≦ a 、 b < 2 ^ 64,1 ≦ n ≦ 1000,且 a 、 b 不同時為 0)。試問 f(a ^ b) 除以 n 的餘數(即 f(a ^ b) 模 n)為何?



範例輸入:
3
1 1 2
2 3 1000
18446744073709551615 18446744073709551615 1000


範例輸出:
1
21
250


解題思維:
以前有提及過皮薩諾週期(Pisano Period,參見這題),其為在模 n 下費氏數列之值的循環節長度。即對於模數 n 存在一數 n' ,使得
f(x) 模 n ≡ f(x 模 n') 模 n
其中 x 可以是任意非負整數,例如本題的 a ^ b。

因為 n 值的範圍很小,所以我們可以預先將所有可能的 n 值之皮薩諾週期求出來建成一個對應的表格。

因此對於輸入進來的 a 、 b 、 n,我們可以先將 a 模 n'(避免求冪過程中溢位)。然後利用快速冪(見這題)求得 a ^ b 模 n' 之值 x。

然後再套用矩陣快速冪(一樣,見這題)求得 f(x) 模 n 之值,此即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作