分數加法最簡形式：杭電 2503 題解

題目：a/b + c/d 最簡分數結果

問題描述： 給定兩個分數 a/b、c/d，求其和並化為最簡形式 e/f。

輸入格式：

• 第一行：測試案例數 T (T ≤ 1000)
• 每行四個正整數 a, b, c, d (0 < a,b,c,d ≤ ...)

輸出格式：

每行輸出兩個整數 e f，表示最簡分數 e/f。

範例：

Input:
2
1 2 1 3
4 3 2 3

Output:
5 6
2 1

解法：通分 + 最大公約數約分

分數加法公式：a/b + c/d = (ad + bc) / bd
分子 m = a*d + b*c，分母 n = b*d
求 gcd(m, n)，分子分母同除以 GCD 即得最簡形式。

C++ 參考實作

#include 

// 遞歸求最大公約數（歐幾里得算法）
int gcd(int m, int n) {
    return n == 0 ? m : gcd(n, m % n);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int a, b, c, d;
        scanf("%d %d %d %d", &a, &b, &c, &d);

        long long m = 1LL * a * d + 1LL * b * c;  // 用 long long 防溢位
        long long n = 1LL * b * d;

        int g = gcd(m, n);
        printf("%lld %lld\n", m / g, n / g);
    }
    return 0;
}

關鍵點提示

1. 資料型別：a,b,c,d 乘積可能超過 int 範圍，建議用 long long 存儲中間結果
2. GCD 實作：遞歸版簡潔高效，非遞歸版同理
3. 邊界情況：結果為整數時（分母為 1），正確輸出如 2 1

複雜度分析

• 時間：O(T * log(max(m,n)))，GCD 為對數級
• 空間：O(1)

此題考察分數運算基礎與 GCD 算法應用，是 ACM 入門經典題型。