e450: 電石爬樓梯
Tags :
Accepted rate : 1人/5人 ( 20% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-10-11 08:55

Content

電石──並非拋入水中會產生乙炔的那樣東西,而是一個人的稱號──在見到東東的事蹟後心生嚮往,決定朝成為爬樓梯大師的目標邁進。

曾幾何時,電石已然爬過八百萬階樓梯,他參加國際爬樓梯大賽並勇奪世界冠軍,一時間名滿天下,眾人聽聞消息無不欣慕。

然而在漫長的磨練中,電石發掘出一項隱藏在腳底下的神秘性質:

若每步只能向上走一階或二階,且總共有 $\color{black}{n}$ 階樓梯,則 $\color{black}{n=1}$ 時有一種走法,$\color{black}{n=2}$ 時有兩種,把 $\color{black}{n=1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 9,\ 10,\ \cdots}$ 的走法數寫下來會是 $\color{black}{1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\ \cdots}$。

然後把每個數都改成除以二的餘數,即 $\color{black}{1,\ 0,\ 1,\ 1,\ 0,\ 1,\ 1,\ 0,\ 1,\ 1,\ \cdots}$,可以觀察到數字以 $\color{black}{1,\ 0,\ 1}$ 的形式重複出現。電石發現無論除以多少,走法數的餘數似乎都會循環,他現在正忙著爬樓梯,所以請你撰寫程式幫忙驗證。

 

Input

只有一個正整數 $\color{black}{n \in \{10,\ 3000,\ 3000000\}}$

Output

輸出共有 $\color{black}{n}$ 列。

第 $\color{black}{k}$ 列輸出走法數除以 $\color{black}{k}$ 時餘數的循環節長度(例如 $\color{black}{k=2}$ 時每 $\color{black}{3}$ 個一循環,循環節長度為 $\color{black}{3}$),假如不會循環,請輸出 $\color{black}{-1}$。

Sample Input
10
Sample Output
1
3
8
6
20
24
16
12
24
60
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (33%): 1.0s , <1K
公開 測資點#1 (34%): 4.0s , <1K
公開 測資點#2 (33%): 1.0s , <1K
Hint :
Tags:
出處:
[管理者:
icube (輸光光)
]


ID User Problem Subject Hit Post Date
19565
2qbingxuan (程式初學者)
e450
Pisano period
80 2019-10-11 01:01