b537. 分數運算-1

Hard Last Update: 2025/05/16

數學

解法一

🔹 反推

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

函數 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$ )，而進入另一種狀態

g(99, 2)

g(99, 2)
= g(99-2, 2) *2
= g(97-2, 2) *2 *2
= g(95-2, 2) *2 *2 *2
= …

可以一起處理 $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;
}