a451. 10229 - Modular Fibonacci
標籤 : 快速冪運算 模數 矩陣 費氏數列
通過比率 : 322人/481人 ( 67% ) [非即時]
評分方式:
Strictly

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

內容
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 的餘數。

輸入說明
輸入包含了多組 n, m.一組一行
輸出說明

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

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

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
26767 seer.2892108 ... (james lyu) a451
1591 2021-08-24 14:35