解法一

🔹 反推

首先 一定要記得約分
用 __gcd() 計算最大公因數作為分母約分

答案會爆 int 需要用 long long

函數 f(k)

根據題目敘述
函數 f(k) 返回兩個值 a, b
a 是分子，b 是分母 ($\frac{a}{b}$)

• k 是奇數時返回 $\frac{1}{f(k-1)}$
  將分子分母分開為 {y, x} ($f(k-1)$ 的倒數)
  (x 是 f(k-1) 的分子，y 是 f(k-1) 的分母)

• k 是偶數時返回 $1 + f(k/2)$
  將分子分母分開為 {x+y, y} (將 $1$ 視為 $\frac{b}{b}$)
  (x 是 f(k/2) 的分子，y 是 f(k/2) 的分母)

pair<int, int> f(int k){
    if(k == 1) return {1, 1};
    
    if(k & 1){
        auto fk = f(k-1);
        return {fk.second, fk.first};
    }
    else{
        auto fk = f(k/2);
        return {fk.first+fk.second, fk.second};
    }
}

回推 g(a, b)

實現 g(a, b) 找回 k

從 f(k) 中觀察到返回值的特性

• 如果 (a, b) = (1, 1)
  k = 1

• 如果 a > b
  那他應該來自 k 為偶數的情況
  {x+y, y} x+y 一定 > y
  

• 如果 a < b
  那他應該來自 k 為奇數的情況
  {y, x} x 一定 > y
  會出現 k 為奇數的情況 代表前一次 k 一定是偶數 (k 是奇數，k-1 不可能也是奇數)
  而 k 是偶數時 {x+y, y}
  交換後 {y, x+y} y 一定 < x+y

最終回推得到

• a = b : k = 1
• a > b : k = g(a-b, b) * 2
• a < b : k = g(b, a) + 1

✅ 完整代碼

評分結果(參考) ： AC (2ms, 356KB)

#include<bits/stdc++.h>
#define int long long
using namespace std;

int g(int a, int b){
    if(a == 1 && b == 1) return 1;

    if(a > b){
        return g(a-b, b) * 2;
    } 
    else{
        return g(b, a) + 1;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b;
    while(cin >> a >> b){
        int c = __gcd(a, b);
        cout << g(a/c, b/c) << "\n";
    }
    
    return 0;
}

解法二、解法一優化版

🔹 合併處理 a > b

$a > b$ 時
$a$ 可能需要減多次 $b$ 才能使得 $a < b$ (或 $a = b$)，而進入另一種狀態

可以一起處理 $a > b$ 的狀況
計算重複處理的次數 q，以及處理後剩餘的數 r
q = a/b, r = a%b，改返回為 g(r, b) * pow(2, q)
這樣便一次處理完了 $a > b$ 的狀況

再用右移 << 優化 : g(r, b)<<q

另外注意 b = 1 的情況 (a 會被整除，導致 r = 0)

✅ 完整代碼

評分結果(參考) ： AC (2ms, 316KB)

#include<bits/stdc++.h>
#define int long long
using namespace std;

int g(int a, int b){
    if(a==1 && b==1) return 1;

    if(a > b){
        int q = a/b;
        int r = a%b;
        
        if(b == 1) return g(r+1, b)<<(q-1);
        else return g(r, b)<<q;
    } 
    else{
        return g(b, a)+1;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b;
    while(cin >> a >> b){
        int c = __gcd(a, b);
        cout << g(a/c, b/c) << "\n";
    }
    
    return 0;
}