題目連結：
題目大意：
定義一個函數 f，其
f(1) = 1；
f(k) = 1 + f(k ÷ 2) ，當 k 為偶數時；
f(k) = 1 ÷ f(k - 1) ，當 k 為奇數時。
輸入有多列，每列給定兩正整數 a 、 b（1 ≦ a 、 b ≦ 60），試問當 k 值為多少時，f(k) 之值 = a ÷ b？
範例輸入：
1 1
2 1
1 2
3 1
1 3
3 2
2 3
4 1
1 4
4 3
30 11
範例輸出：
1
2
3
4
5
6
7
8
9
10
236
解題思維：
我們可以觀察到：
當 k 為奇數時，f(k) 之值 ≦ 1；當 k 為偶數時，f(k) > 1。
因此，當我們看到一個分數 a ÷ b 時，我們雖然不知道此時的 k 值為多少，但是我們可以藉由判斷 a 與 b 的大小關係而得知奇偶性。
以 4 ÷ 3 來說：
因為 4 > 3，所以 f(k) = 4 ÷ 3 的 k 值為偶數，因此可以推得 f(k) 來自於 1 + f(k1)（k1 = k ÷ 2），所以 f(k1) = 1 ÷ 3；
因為 1 < 3，所以 f(k1) = 1 ÷ 3 的 k1 為奇數，因此 f(k1) = 1 ÷ f(k2)（k2 = k1 - 1），所以 f(k2) = 3 ÷ 1；
因為 3 > 1，所以 f(k2) = 3 ÷ 1 的 k2 為偶數，因此 f(k2) = 1 + f(k3)（k3 = k2 ÷ 2），所以 f(k3) = 2 ÷ 1；
因為 2 > 1，所以 f(k3) = 2 ÷ 1 的 k3 為偶數，因此 f(k3) = 1 + f(k4)（k4 = k3 ÷ 2），所以 f(k4) = 1 ÷ 1；
而因為 1 = 1，所以我們已經退回到 f(1) 了（根據函數 f 之定義），所以我們從此步驟往回推，可以推得：
k4 = 1
k3 = k4 × 2 = 2
k2 = k3 × 2 = 4
k1 = k2 + 1 = 5
k = k1 × 2 = 10
因此 f(10) = 4 ÷ 3。
而其他 a ÷ b 之值也是同理，且就算 a 、 b 不互質也沒關係，只要當 a = b 時，就代表我們已經遞迴到 f(1) 了（只有 f(1) 是分子等於分母）。而那些各種 k 值之遞迴資訊可以使用堆疊（Stack）去存。或是直接使用遞迴的架構去寫如下：
F(x, y):
當 x = y 時，回傳 1；
當 x > y 時，回傳 F(a - b, b) × 2；
當 x < y 時，回傳 F(b, a) + 1；
而呼叫 F(a, b) 即可求得答案（因為遞迴的基本架構即是堆疊）。
而需要注意的是，可以看到當 k = 2 ^ n （n ≧ 0）時，f(k) = (n + 1) ÷ 1，因為 a 、 b 最大到 60 ，所以可以出現 60 、 1 這種輸入，而此時的 k 值為
576,460,752,303,423,488
很明顯地會超過 C/C++ 之 int 整數（32 位元有號整數）型態，因此請記得使用 long long 型態（64 位元有號整數）儲存。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
