a451: 10229 - Modular Fibonacci
Tags : 快速冪運算 模數 矩陣 費氏數列
Accepted rate : 157人/204人 ( 77% ) [非即時]
評分方式:
Strictly

最近更新 : 2012-06-16 17:43

Content
Problem A: Modular Fibonacci

斐波那契數列 (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...) 的定義如以下遞迴:

F0 = 0
F1 = 1
Fi = Fi-1 + Fi-2 for i>1

給你 n, m,其中 0 <= n <= 2147483647 , 0 <= m < 20.

請寫出一個程式可以計算 Mn = Fn mod 2m的程式。

注意到 a mod b 的結果為 a 除以 b 的餘數。

Input
輸入包含了多組 n, m.一組一行
Output

輸出每一個 Mn , 每個 Mn 單獨一行

Sample Input #1
11 7
11 6
Sample Output #1
89
25
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 3.0s , <1M
Hint :
何不先完成 D481
Tags:
快速冪運算 模數 矩陣 費氏數列
出處:
UVa10299 [管理者:
grd (保持好奇心)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」