hdoj2503 最大公约数

题目描述：

Problem Description
给你2个分数，求他们的和，并要求和为最简形式。
Input
输入首先包含一个正整数T（T<=1000），表示有T组测试数据，然后是T行数据，每行包含四个正整数a,b,c,d（0<a,b,c,d<1000），表示两个分数a/b 和 c/d。
Output
对于每组测试数据，输出两个整数e和f，表示a/b + c/d的最简化结果是e/f，每组输出占一行。
Sample Input
2
1 2 1 3
4 3 2 3
Sample Output
5 6
2 1

看到此题，我的第一反应就是小学五年级的分母加减法，其中通分需要用两个分母的最小公倍数，而约分需要用分子和分母的最大公约数。此题就是模拟分母加减法的运算过程。一说到最大公约数，当然就得用辗转相除法了。

参考代码：

#include <iostream>
using namespace std;
int gcd(int b,int d) {
    if (d == 0) {
        return b;
    }
    else {
        return gcd(d,b%d);
    }
}
int lcm(int b,int d) {
    int g = gcd(b,d);
    int l = (b * d) / g;
    return l;
}
void result(int a,int b,int c,int d) {
    int fenmu,fenzi;
    int g;
    if (b == d) {
        fenzi = a + c;
        fenmu = b;
        g = gcd(fenzi,fenmu);
        fenzi /= g;
        fenmu /= g;
    }
    else {
        fenmu = lcm(b,d);
        int fenzi1 = a * (fenmu / b);
        int fenzi2 = c * (fenmu / d);
        fenzi = fenzi1 + fenzi2;
        g = gcd(fenzi,fenmu);
        fenzi /= g;
        fenmu /= g;
    }
    cout << fenzi << " " << fenmu << endl;
}
int main() {
    int t;
    int a,b,c,d;
    cin >> t;
    while (t--) {
        cin >> a >> b >> c >> d;
        result(a,b,c,d);
    }
    return 0;
}

分析完毕，欢迎交流。