HDU 2503 題解：分數加法與約分

題目大意

輸入 t 組測試數據，每組給四個整數 a b c d，計算 a/b + c/d 並輸出最簡分數形式（分子 分母）。

算法

1. 通分：分子 x = a*d + b*c，分母 y = b*d。
2. 求最大公約數 g = gcd(x, y)。
3. 輸出 x/g y/g。

AC 代碼

#include <cstdio>

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        int x = a * d + b * c;
        int y = b * d;
        int g = gcd(x, y);
        printf("%d %d\n", x / g, y / g);
    }
    return 0;
}

複雜度

• 時間：O(t * log(max(x,y)))，輾轉相除法極快。
• 空間：O(1)。