b461: 【我愛Möbius】之Fibonacci之夢
Tags : 數論基礎
Accepted rate : 7人/10人 ( 70% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-07-28 02:15

Content

小時候睡不著覺的時候,媽媽就教我們數數,$0,1,1,2,3,5,8,13,21,34,55,89,144,\dots$一直數下去,直到我們睡著。多麼溫馨的畫面啊!

這裡,為了不引起歧義,我們定義一遍Fibonacci數列。

\[
F_n=\begin{cases}
n, & n=0,1 \\
F_{n-1}+F_{n-2}, & n \geq 2
\end{cases}
\]

我就經常睡不著覺,在睡不著覺的時候就開始學著像上面那樣數數,$0,1,1,2,3,5,8,13,21,34,55,89,144,\dots$一直數下去。不知道數了多久,我就已經呼呼大睡了。 

第二天早上起來,睡眼迷離的我只能依稀記得最後數的那個數字是多少。可是畢竟人腦記憶有限,我只能記得這個數字的最後$K$個數位(當然,我是一個正常人,所以當然是用$10$進制來數數。)比如我數到$144$且我只能記得這個數字的最後$K=2$位,那麼我第二天就只是記得$44$這個數字。

為了知道自己從躺上床到底經過了多久才睡著,我現在只能通過已知的最後一個數字(就是頭一天數數的時候最後一個數到的數的後$K$位)來大概估計這個時間。也就是說,通過我所知的唯一的數字,來倒推出我到底數了多少個數字,即已知$x$,求$n$,使得$F_n \equiv x (\mod 10^K)$,那麼$n+1$就是我昨晚一共數了的數字個數。

我是一個樂觀主義者,我當然會認為我會盡量快睡著,所以如果存在多個$n$滿足條件,我會取最小的那個$n$。

Input

第一行有兩個正整數$K(1 \leq K \leq 18)$和$T(1 \leq T \leq 100)$,分別表示我只能記得一個數字的后$K$位,以及我連續失眠了$T$天。

接下來$T$行,每行一個長度為$K$的整數$x(0 \leq x < 10^K)$,表示這天晚上我數到最後的那個數字。 

Output
對於每一天,輸出一個數字,表示我至少數了多少個數字。如果我根本不可能數到$x$,請輸出"You've slept foolish!",告訴我“我睡傻了”。
Sample Input #1
3 3
001
144
004
Sample Output #1
2
13
You've slept foolish!
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1K
公開 測資點#4 (5%): 2.0s , <1K
公開 測資點#5 (5%): 2.0s , <1K
公開 測資點#6 (5%): 2.0s , <1K
公開 測資點#7 (5%): 2.0s , <1K
公開 測資點#8 (5%): 3.0s , <1M
公開 測資點#9 (5%): 3.0s , <1M
公開 測資點#10 (5%): 3.0s , <1M
公開 測資點#11 (5%): 3.0s , <1M
公開 測資點#12 (5%): 5.0s , <1M
公開 測資點#13 (5%): 5.0s , <1M
公開 測資點#14 (5%): 5.0s , <1M
公開 測資點#15 (5%): 5.0s , <1M
公開 測資點#16 (10%): 5.0s , <1M
公開 測資點#17 (10%): 10.0s , <1M
Hint :

第$i$個測資點的$K=i$。

這是【我愛Möbius】系列的第四題,上一題是【我愛Möbius】之最大公約數求和,未完待續。 

Tags:
數論基礎
出處:
[管理者:
liouzhou_101 (王启圣)
]


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