PAT 1081

题目 ： Rational Sum

分值 ： 20
难度 ： 中等题
思路 ： 一开始看到long int 有点懵, 后来发现只要你每次 两两通分相加然后约分就好
知识 ： 两个数的最大公因数求法吗,如果你爆搜 会超时的,在代码里面两种都有,有兴趣可以尝试

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
using namespace std ;

long find(long a , long  b )   // 辗转相除找最大公因数   不会超时 优化方案
{
    long r ;
    while(b != 0)
    {
        r = a% b ;
        a = b  ;
        b = r ;
    }
    return a ;
}
long find1(long a , long  b )   //爆搜找最大公因数   会超时     普通方案
{
    long min = a>b ? b:a ;
    for(long i = b ; i >=1 ;i--)
    {
        if(!(a%i) && !(b%i))
            return i ;
    }
    return 1;
}
void Add(long  & a ,long & b ,long A,long B )
{
    int flag =1 ;
    long fenzi = a*B + b*A;
    long fenmu = b * B ;
    if(fenzi < 0)
    {
        flag =-1  ;
        fenzi = -fenzi ;
    }
    long zdgys = find(fenzi , fenmu ) ;
    a =flag* fenzi/zdgys ;
    b =fenmu /zdgys ;
}
int main()
{
    int N ;
    cin >> N ;
    long int a , b , A,B ;
    scanf("%ld/%ld" , & a , &b ) ;
    for(int i =1 ; i< N ; i++)
    {
        scanf("%ld/%ld" , & A, &B ) ;
        Add(a,b,A,B);
    }
    if(a==0)
        cout<<"0"<<endl ;
    else if(b==1)
        cout<<a<<endl ;
    else if(a/b)
    {
        cout << a/b <<" "<<a%b<<"/"<<b<<endl ;
    }
    else cout << a <<"/"<<b ;
}