網頁

2014年1月24日 星期五

UVa 834 Continued Fraction

本題題目連結

想法:
  這題可以自己舉幾個例子算出分數,找出規則,解法如下,由題目Example,從(43,19)逆推回去
  1. 首先2的話就是43/19=2,43%19=5,那麼現在[2;] & (5,19)
  2. 19/5=3,19%5=4,得到[2;3] & (5,4)
  3. 倒數的緣故,交換兩數,現在[2;3] & (4,5)
  4. 重複2~3步驟,直到第一個數為1