L1_009 N个分数形式有理数求和

本题的要求很简单，就是求N个数字的和。麻烦的是，这些数字是以有理数“分子/分母”的形式给出的，你输出的和也必须是有理数的形式。

输入格式：
输入第一行给出一个正整数N（<=100）。随后一行按格式“a1/b1 a2/b2 ...”给出N个有理数。题目保证所有分子和分母都在长整型范围内。另外，负数的符号一定出现在分子前面。

输出格式：
输出上述数字和的最简形式 —— 即将结果写成“整数部分 分数部分”，其中分数部分写成“分子/分母”，要求分子小于分母，且它们没有公因子。如果结果的整数部分为0，则只输出分数部分。

• 思路
• 辗转法求最大公因数
  a与b的最大公因数
  a=k1b+r1,若r1=0，则b为最大公因数，否则
  b=k2r1+r2,若r2=0，则r1为最大公约数，a=k1(k2r1)+r1=(k1k2+1)r1
  否则继续r1=k3r2+r3....
• 注意用long来存，即使约分

#include <iostream>
#include <string>
using namespace std;
long fz1=0, fz2, fm1=1, fm2, fz, fm;
int integ = 0;
int gcd(int a, int b)
{
    int max, min;
    if (a > b)
    {max = a;min = b;}
    else
    {max = b;min = a;}
    while (max%min != 0)
    {
        int temp = max;
        max = min;
        min = temp%min;
    }
    return min;
}
void yf()
{
    integ += fz / fm;
    fz = fz - fm*(fz / fm);
    if (fz != 0) {//注意此处的判断
        int gys = gcd(fm, fz);
        fz = fz / gys;
        fm = fm / gys;
    }
}
int main()
{
    int n;
    cin >> n;
    string fs;
    for (int i = 1; i <= n; ++i)
    {
        cin >> fs;
        int fh = fs.find('/');
        string sfz = fs.substr(0, fh);
        string sfm = fs.substr(fh + 1, fs.size() - fh - 1);
        fz2 = atoi(sfz.c_str());
        fm2 = atoi(sfm.c_str());
        fz = fz1*fm2 + fz2*fm1;
        fm = fm1*fm2;
        yf();
        fz1 = fz;
        fm1 = fm;
    }
    if (integ != 0)
        cout << integ ;
    if (fz != 0) {
        if (integ != 0)
            cout << " ";
        cout << fz1 << "/" << fm1 ;
    }
    if (integ == 0 && fz == 0)//一开始没考虑这个就只有部分正确
        cout << 0;
    system("pause");
    return 0;
}