因此,我們了解到單位分數(unit fraction,即分子為$1$的分數)的乘法其實是整數除法的運算。
既然提到了單位分數這種分子為 $1$ 的特殊分數,就不得不提一下古埃及人他們對於分數的運算以及記錄方法,
古埃及人的乘除法運算十分特別,文獻 "Rhind Mathematical Papyrus" 中記載,他們的乘除法是用一種稱作"RMP 2/n table"的表格來計算。
當兩數無法整除時,古埃及人也會如同現在的我們一樣,用分數表示剩餘的部分,
然而,由於這種"RMP 2/n table"的特性,古埃及人將會用單位分數之和來表示而非我們現在慣用的分數,
舉例來說,對於 ${\frac{3}{5}}$ 而言,古埃及人將會寫成 ${\frac{1}{2}}+{\frac{1}{10}}$,
那 ${\frac{2}{5}}$ 呢? 古埃及人會寫成 ${\frac{1}{5}}+{\frac{1}{5}}$,吧? 才怪,他們會寫成${\frac{1}{3}}+{\frac{1}{15}}$... (他們不會重複使用同一種單位分數)
由於這個緣故,最近在研究這個部份的曉涵感到非常的困擾,
因為她沒有辦法在很快的時間內判斷出一個常見的分數在古埃及人的習慣下應該寫成什麼!!
而聽到了這件事的你,決定寫個程式幫幫她,讓他能很快的將所有分數轉換成古埃及人的表示法。
給定兩個正整數 $q$, $p$,代表一個真分數 ${\frac{q}{p}}$ ($1≦q < p≦200000$),代表要轉換的分數。
輸出一行式子,表示應如何將輸入的分數分解成數個相異的單位分數和。
若分解成兩個以上的單位分數,應將較大的數置於前面。(格式請參考 Sample Output)
(注意:如果能表示成多種單位分數之和,請輸出第一個分數最大的那一組,如果第一個一樣大,則比較第二個...以此類推。)
文獻 "Rhind Mathematical Papyrus":
( 圖片來源: Wikipedia )
原TIOJ1538 / Problem Setter: Skyly
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 6 |
2 | 1 | 6 |
3 | 2 | 6 |
4 | 3 | 6 |
5 | 4 | 6 |
6 | 5 | 6 |
7 | 6 | 6 |
8 | 7 | 6 |
9 | 8 | 6 |
10 | 9 | 6 |
11 | 10 | 6 |
12 | 11 | 6 |
13 | 12 | 6 |
14 | 13 | 6 |
15 | 14 | 16 |