提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

1081 Rational Sum

sum
2023-09-11 14:22:44 时间

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 (≤), 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

题意：

　　给出几个分数，求这些分数的和，然后按照带分数的格式输出。

思路：

　　将分母通分，分子相加。用到了GCD和LCM的知识。最后一组测试点会卡0，这种特殊的情况。另外GCD函数不用考虑两个数谁大谁小。

Code：

#include <bits/stdc++.h>

using namespace std;

struct Number {
    int sign;
    long long numerator;
    long long denominator;
};

long long gcdFun(long long x, long long y) {
    if (x == 0 || y == 0)
        return x == 0 ? y : x;
    else
        return x > y ? gcdFun(y, x % y) : gcdFun(x, y % x);
}

int main() {
    int n;
    cin >> n;
    int gcd = 1;
    stack<Number> s;
    for (int i = 0; i < n; ++i) {
        string str;
        int sign = 1;
        long long numerator, denominator;
        cin >> str;
        if (str[0] == '-') {
            sign = -1;
            str = str.substr(1);
        }
        int pos = str.find('/');
        numerator = stoll(str.substr(0, pos));
        denominator = stoll(str.substr(pos + 1));
        int gcd = gcdFun(numerator, denominator);
        if (gcd == 0) continue;
        s.push({sign, numerator / gcd, denominator / gcd});
    }
    while (s.size() > 1) {
        Number num1 = s.top();
        s.pop();
        Number num2 = s.top();
        s.pop();
        long long gcd = gcdFun(num1.denominator, num2.denominator);
        long long lcm = num1.denominator * num2.denominator / gcd;
        long long mult1 = lcm / num1.denominator;
        long long mult2 = lcm / num2.denominator;
        long long sumNumerator = num1.sign * num1.numerator * mult1 +
                                 num2.sign * num2.numerator * mult2;
        int sign = 1;
        if (sumNumerator < 0) {
            sign = -1;
            sumNumerator = abs(sumNumerator);
        }
        gcd = gcdFun(sumNumerator, lcm);
        s.push({sign, sumNumerator / gcd, lcm / gcd});
    }
    Number ans = s.top();
    long long integer = ans.numerator / ans.denominator;
    long long fractional = ans.numerator % ans.denominator;
    if (integer != 0 && fractional != 0) {
        cout << integer << " " << fractional << "/" << ans.denominator << endl;
    } else if (integer != 0) {
        cout << integer << endl;
    } else if (fractional != 0) {
        cout << fractional << "/" << ans.denominator << endl;
    } else
        cout << "0" << endl;

    return 0;
}

 

相关文章