TopCoder

M_SQRT
$\textbf{W}\symbfit{elcome~to~}\Huge\color{blue}{\mathbfcal{TIOJ}}%Caidorz$

User's AC Ratio

93.6% (161/172)

Submission's AC Ratio

48.2% (236/490)

Tags

Description

  連分數有許多不為人知的應用,一開始一位印度數學家利用連分數解出了 ax+by=c的一次不定方程式,連分數還跟我們日常生活中的曆法有密切的關係,那什麼是連分數呢?

  連分數一般如下面形式:


  連分數有四種,一種是無窮連分數可以一直延展下去,一種是有窮連分數,而連分數又可分為簡單連分數,即分子部份永遠是 1 ,另一種是非簡單連分數,分子部份是由其他數字所組成。每一個有理數都可以用簡單有窮連分數來表示:

簡單有窮連分數不會一直延展下去,當子分數的分母為一整數時,就要停止。

現在輸入P和Q,請你幫忙將P/Q化為連分數吧。

Input Format

輸入檔第一行有一個數字N代表有幾組測試資料,接下來N行,每行會有兩個數字分別代表 P 和 Q (0 ≤ P,Q ≤ 2147483647 且 Q ≠ 0)。

Output Format

每組測試資料輸出一行,輸出為下面格式:

P/Q = a+1/{b+1/{c+1/{d+...}}}

其中a是非負整數,b,c,d,...都是正整數。

Sample Input 1

3
103 24
21 73
4 2

Sample Output 1

103/24 = 4+1/{3+1/{2+1/3}}
21/73 = 0+1/{3+1/{2+1/10}}
4/2 = 2

Hints

※2007/10/07:題目敘述修正,感謝seanwu和akira兩位大大。

Problem Source

原TIOJ1040 / NPSC2003初賽(prob C)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1