UVA-948 - Fibonaccimal Base

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！
• 本題選為「20160524 大學程式能力檢定 CPE」題目。
• 相同題目：ZOJ-a134

題意概要

題目給定一個以十進位為基底的數值，試求：該數值以費式數列 (Fibonacci Series) 為基底的表示式。

• 分析：本題為費氏數列的應用，先建立一個陣列存取費氏數列，題目已經給定輸入測資的範圍不超過 $100,000,000$，因此可以找到最大到費氏數列中第 $40$ 個數值。將題目給定的數值「從可被費氏數列的最大數值」逐一往小減去，並同時印出 1 或 0 表示是否可以減去。

Input

The first line of input contains a single number $N$, representing the quantity of numbers that follow ($1 \le N \le 500$). Than follow exactly $N$ lines, each one containing a single positive integer smaller than $100,000,000$. These numbers can come in any order.

Output

You should output a single line for each of the $N$ integers in the input, with the format DEC_BASE = FIB_BASE (fib). DEC_BASE is the original number in decimal base and FIB_BASE is its representation in Fibonaccimal base. See the sample output for an example.

Sample Input

10
1
2
3
4
5
6
7
8
9
10

Sample Output

1 = 1 (fib)
2 = 10 (fib)
3 = 100 (fib)
4 = 101 (fib)
5 = 1000 (fib)
6 = 1001 (fib)
7 = 1010 (fib)
8 = 10000 (fib)
9 = 10001 (fib)
10 = 10010 (fib)