PAT甲级1081 Rational Sum (20 分)

1081 Rational Sum (20 分)

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

结尾无空行

#include <iostream>
#include <vector>
using namespace std;
vector<long> numerator;
vector<long> denominator;
long gcd(long a,long b)  //求最大公约数
{
    if(b == 0)
        return a;
    return gcd(b,a%b);
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        char c;
        long a,b;
        cin>>a>>c>>b;
        numerator.push_back(a);
        denominator.push_back(b);
    }
    int pos=n-1;
    while(numerator.size()>1)
    {

        long a1=numerator[pos];
        numerator.pop_back();
        long a2=numerator[pos-1];
        numerator.pop_back();
        long b1=denominator[pos];
        denominator.pop_back();
        long b2=denominator[pos-1];
        denominator.pop_back();
        long same_min=gcd(max(b1,b2),min(b1,b2));
        long same_max=b1*b2/same_min;
        long resa=a1*(same_max/b1)+a2*(same_max/b2);
        long resb=same_max;
        long res_same_min=gcd(max(resa,resb),min(resa,resb));
        resa=resa/res_same_min;
        resb=resb/res_same_min;
        numerator.push_back(resa);
        denominator.push_back(resb);
        pos--;
    }
    if(denominator[0]==1)
        cout<<numerator[0]<<endl;
    else
    {
        int res1=numerator[0]/denominator[0];
        int res2=numerator[0]-res1*denominator[0];
        if(res1!=0)
            cout<<res1<<" ";
        cout<<res2<<"/"<<denominator[0]<<endl;
    }
    return 0;
}

上一篇:密码类


下一篇:APP Https双向认证抓包_android