a371. 神秘數字（Number） - 彰化精誠中學

內容

布魯特˙佛斯博士是一個對於數字的專家，根據他多年來對於數字的研究，他發現對於任意的三元數組(n,a,b)，計算其神秘度的方法可以用一個演算法來表示，其虛擬碼如下：

Function Find(integer n, function func)

If n=0：

For i = 1 to a do func()

Elseif n=1 ：

For i = 1 to b do func()

Else：

Find(n‐1,Find(n‐2,func))

Function Main

Find(n, mysterious)

而(n,a,b)之神秘度即為在該演算法執行過程中，函式 mysterious 被呼叫的次數。

儘管布魯特博士對於數字的性質十分擅長，他對於程式設計一竅不通，所以他希望你能夠幫助他計算某個三元數組(n,a,b)的神秘度。

另外，因為布魯特博士不希望看到太大的數字，你只要跟他講神秘度除以 p 的餘數就可以了

輸入說明

第一行有一個數字 T（T ≤ 30），表示共有幾組測資。

接下來 T 行每行皆包含以空白隔開的四個數字 n, a, b, p（1 ≤ n, a, b, p ≤ 1000000000， a, b 皆與 p 互質），表示所需計算之三元數組。

輸出說明

輸出 T 行，每行一個整數，代表所對應三元數組神秘度除以 p 的餘數。

範例輸入 #1

1
2 2 2 113

範例輸出 #1

範例輸入 #2

2
1000 1 1 123
1000 1 1 456

範例輸出 #2

1
1

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <1K
公開測資點#2 (20%): 1.0s , <1K
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (20%): 1.0s , <1M

提示：

標籤:

出處:

[管理者：

iris@stu.cch... (iris)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」