C4top-N个数求和（分数求和模拟）

今天药忘吃喽~ 2022-10-01 00:51 154阅读 0赞

N个数求和

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

### 输入格式： ###

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

### 输出格式： ###

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

### 输入样例1： ###

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

### 输出样例1： ###

3 1/3

### 输入样例2： ###

2
    4/3 2/3

### 输出样例2： ###

### 输入样例3： ###

3
    1/3 -1/6 1/8

### 输出样例3： ###

7/24

*  时间限制：400ms
 *  内存限制：64MB
 *  代码长度限制：16kB
 *  判题程序：系统默认
 *  作者：陈越
 *  单位：浙江大学

#### 题目判定 ####

##### 解题思路 #####

我的思路就是先把所有分数通分，然后计算他们分子的和，最后 分情况讨论是否假分数。

注意两个坑点：①分子为0；②只有一组测试数据。

##### 解题程序 #####

#include<bits/stdc++.h>
    using namespace std;
    #define INF 0xfffffff
    #define MAXN 1100
    
    struct Node
    {
        long long x,y;//分子分母
    } a[MAXN];
    
    long long gcd(long long a,long long b)//最大公约数
    {
        return (a%b!=0?(gcd(b,a%b)):b);
    }
    long long lcm(long long a,long long b)//最小公倍数
    {
        long long t=gcd(a,b);
        return (a*b/t);
    }
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
    //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        long long n;
        cin>>n;
        for(long long i=0; i<n; ++i)
        {
            char str[10];
            cin>>str;
            long long len=strlen(str);
            a[i].x=a[i].y=0;
            long long minu=1;//是否负数
            bool flag=true;
            for(long long j=0; j<len; ++j)
            {
                if(str[j]=='-')
                {
                    minu=-1;
                    continue;
                }
                if(str[j]=='/')
                {
                    flag=false;
                    continue;
                }
                if(flag)
                {
                    a[i].x*=10;
                    a[i].x+=str[j]-'0';
                }
                else
                {
                    a[i].y*=10;
                    a[i].y+=str[j]-'0';
                }
            }
            if(minu==-1) a[i].x*=minu;//负数
            //cout<<a[i].x<<"/"<<a[i].y<<endl;
            long long t=gcd(a[i].x,a[i].y);
            if(t!=1) a[i].x/=t,a[i].y/=t;
        }
        long long fz=0,fm=0;//分子分母
        if(n==1)//①只有一组数据
        {
            fz=a[0].x,fm=a[0].y;
        }
        else
        {
            fm=lcm(a[0].y,a[1].y);
            for(long long i=1; i<n; ++i)
            {
                long long t=lcm(fm,a[i].y);
                fm=t;
            }
            //cout<<lc<<endl;
            fz=0;//分子
            for(long long i=0; i<n; ++i)
            {
                long long t=fm/a[i].y;
                a[i].y*=t;
                a[i].x*=t;
                fz+=a[i].x;
                //cout<<a[i].x<<"/"<<a[i].y<<endl;
            }
        }
        if(fz==0)//②分子为0，结果为0
        {
            cout<<"0"<<endl;
        }
        else
        {
            long long ans=fz/fm;
            //cout<<ans<<endl;
            if(ans)//③假分数
            {
                fz-=ans*fm;
                if(fz==0)
                {
                    cout<<ans<<endl;
                }
                else
                {
                    long long t=gcd(fz,fm);
                    fz/=t,fm/=t;
                    cout<<ans<<" "<<fz<<"/"<<fm<<endl;
                }
            }
            else//④真分数
            {
                long long t=gcd(fz,fm);
                fz/=t,fm/=t;
                cout<<fz<<"/"<<fm<<endl;
            }
        }
        return 0;
    }