HDU 2503 a/b + c/d — 分數加法與化簡

題目要求：給定兩個分數 a/b 與 c/d，求其和並化為最簡分數。輸入 T 組測試數據（T ≤ 1000），每組四個正整數 a,b,c,d（0 < a,b,c,d ≤ 2^31-1），輸出化簡後的分子 分母。

數學原理

分數加法：

a/b + c/d = (a*d + c*b) / (b*d)

化簡：分子分母同時除以其最大公約數 (GCD)。

GCD 計算採用輾轉相除法（歐幾里得算法）：

gcd(a, b) = gcd(b, a % b)  直到 b == 0，則 a 為 GCD

Java 參考實現

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            long a = sc.nextLong();
            long b = sc.nextLong();
            long c = sc.nextLong();
            long d = sc.nextLong();

            // 分子分母可能超 32 位，用 long
            long num = a * d + c * b; // 分子
            long den = b * d;         // 分母

            // 確保 num >= den 便於輾轉相除（不影響 GCD 結果）
            if (den > num) {
                long tmp = num; num = den; den = tmp;
            }

            // 計算 GCD
            long g = gcd(num, den);

            // 輸出最簡分數
            System.out.println((num / g) + " " + (den / g));
        }
    }

    static long gcd(long a, long b) {
        while (b != 0) {
            long r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}

關鍵細節

1. 溢出防範：a*d、b*d 可能超過 32 位有符號整數範圍，必須用 64 位整數（long/int64_t）。
2. a/b + c/d 的通分分母 b*d 可能很大，但 GCD 算法對大數同樣高效（對數時間）。
3. 輸出順序：題目未要求分子 < 分母，直接輸出化簡後的分子 分母即可。
4. 測試數據組數 T ≤ 1000，總時間複雜度 O(T log max(a,b,c,d)) 極易通過。

C++ 版本速查

#include 
using namespace std;
using int64 = long long;

int64 gcd(int64 a, int64 b) { return b ? gcd(b, a % b) : a; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int64 a, b, c, d;
        cin >> a >> b >> c >> d;
        int64 num = a * d + c * b;
        int64 den = b * d;
        int64 g = gcd(num, den);
        cout << num / g << ' ' << den / g << '\n';
    }
    return 0;
}