e299: PF. Fibnocci of Fibnocci(費⽒數列的費⽒數列)
Tags :
Accepted rate : 7人/12人 ( 58% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-07-16 16:23

Content

⼤家有看過迪⼠尼的⼩美⼈⿂2 嗎?裡⾯有⼀個反派廚師,因為他體型⽐較魁梧,⼤家都叫他Fat 廚。⽽他有位朋友叫做Fib 廚,因為他是位很喜歡費⽒數列(Fibonacci sequence) 的廚師,他平時做料理之中的空閒時間都會默背費⽒數列打發時間。
今天Fat 廚久違的拜訪Fib 廚,在討論完兩者的最近料理⼼得,Fat 廚想試試Fib 廚對費⽒數列有多了解,所以他就隨⼝問了Fib 廚:$fib(15442) mod M$,$M = 1000000007$。沒想到,Fib 廚⾮常輕鬆就回答出來了,還說這種題⽬⼀點也沒有挑戰性,於是,Fat 廚就改問了這個問題:
$fib(fib(15442)) mod M$的答案是多少。這個問題可難倒Fib 廚了,所以為了以後都能回答出這個問題,他想請你幫幫他寫個程式,能夠算出$fib(fib(x)) mod M$。
為了幫助你可以更容易寫出程式,Fib 廚提供了⼀些關於fibnocci 的知識:我們可以找到⼀個
$M’$使得$fib(fib(x))$ $mod$ $M$ $=$ $fib(fib(x)$ $mod$ $M’)$ $mod$ $M$,⽽$M’\leq 10M$。

Input

輸⼊第⼀⾏有⼀個正整數$n$,代表接下來有幾組測試資料。接下來每組測資有⼀個整數$x$。

$1 \leq n \leq 10^5$
$0 \leq x \leq 10^{15}$

Output

對於每組測資,輸出⼀⾏⼀個數字:$fib(fib(x)) % 1000000007$。

Sample Input
6
1
1
2
3
5
8
Sample Output
1
1
1
1
5
10946
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <10M
Hint :
Tags:
出處:
2019 NCTU PCCA Winter [管理者:
qqrainbow (愛蜜莉雅 準•指考戰士)
]


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