Given N rational numbers in the form numerator/denominator, you are supposed to calculate their sum.

Input Specification:

Each input file contains one test case. Each case starts with a positive integer N (≤100), followed in the next line N rational numbers a1/b1 a2/b2 ... where all the numerators and denominators are in the range of long int. If there is a negative number, then the sign must appear in front of the numerator.

Output Specification:

For each test case, output the sum in the simplest form integer numerator/denominator where integer is the integer part of the sum, numerator < denominator, and the numerator and the denominator have no common factor. You must output only the fractional part if the integer part is 0.

Sample Input 1:

5
2/5 4/15 1/30 -2/60 8/3

Sample Output 1:

3 1/3

Sample Input 2:

2
4/3 2/3

Sample Output 2:

2

Sample Input 3:

3
1/3 -1/6 1/8

Sample Output 3:

7/24

注意点

  • 数据范围为 int，但是两个分母相乘时，可能超出 int，最大可以达到 long long，所以如果使用 int，就会溢出，得到“答案错误”
  • 必须在每一步加法后都进行约分，如果等全部加完后才约分，则会溢出
#include <cstdio>
#include <algorithm>
using namespace std;

struct Num {
    long long a, b;
} temp, ans;

long long gcd(long long a, long long b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

void simplify(Num &n) {
    if (n.b < 0) {
        n.a = -n.a;
        n.b = -n.b;
    }
    if (n.a == 0) {
        n.b = 1;
    } else {
        int d = gcd(abs(n.a), abs(n.b));
        n.a /= d;
        n.b /= d;
    }
}

Num add(Num &n1, Num &n2) {
    Num ret;
    ret.a = n1.a * n2.b + n2.a * n1.b;
    ret.b = n1.b * n2.b;
    simplify(ret);
    return ret;
}

int main() {
    int n;
    scanf("%d %lld/%lld", &n, &ans.a, &ans.b);
    simplify(ans);
    for (int i = 1; i < n; i++) {
        scanf("%lld/%lld", &temp.a, &temp.b);
        ans = add(ans, temp);
    }
    if (ans.b == 1) {
        printf("%lld", ans.a);
    } else if (ans.a > ans.b) {
        printf("%lld %lld/%lld", ans.a / ans.b, ans.a % ans.b, ans.b);
    } else {
        printf("%lld/%lld", ans.a, ans.b);
    }
    return 0;
}