PAT-ADVANCED1081——Rational Sum

我的PAT-ADVANCED代码仓：https://github.com/617076674/PAT-ADVANCED

原题链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805386161274880

题目描述：

题目翻译：

1081 有理数的和

给定分子/分母形式的N个有理数，你需要计算它们的总和。

输入格式：

每个输入文件包含一个测试用例。对每个测试用例，第一行包含一个正整数N(<=100)，接下来一行紧跟着N个有理数a1/b1 a2/b2 ...，其中分子和分母都在long int型范围内。如果有负号，负号一定出现在分子上。

输出格式：

对每个测试用例，以最简形式——integer numerator/denominator输出和，其中integer是和的整数部分，numerator < denominator且numerator和denominator没有公约数。如果整数部分integer是0，你只需要输出分数部分。

输入样例1：

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

输出样例1：

3 1/3

输入样例2：

2
4/3 2/3

输出样例2：

2

输入样例3：

3
1/3 -1/6 1/8

输出样例3：

7/24

知识点：欧几里德算法求最大公约数

思路：将分数通分后两两相加

注意点：

（1）用欧几里得算法求分子和分母的最大公约数时，需要传进去两个非负数。

（2）结果分子为0时，需要直接输出0，并return 0结束main函数（测试点4就是这样的一组测试用例）。

时间复杂度是O(N)。空间复杂度是O(1)。

C++代码：

#include<iostream>
#include<cmath>

using namespace std;

struct digit {
	long long numerator;
	long long denominator;
	digit() {};
	digit(long long _numerator, long long _denominator) : numerator(_numerator), denominator(_denominator) {};
};

long long gcd(long long a, long long b);
digit add(digit d1, digit d2);

int main() {
	int N;
	scanf("%d", &N);
	digit result = digit(0, 1);
	digit tempDigit;
	for(int i = 0; i < N; i++) {
		scanf("%lld/%lld", &tempDigit.numerator, &tempDigit.denominator);
		result = add(result, tempDigit);
	}
	if(result.numerator == 0){
		printf("0\n");
		return 0;
	}
	if(result.numerator / result.denominator != 0) {
		printf("%lld", result.numerator / result.denominator);
	}
	if(result.numerator % result.denominator != 0) {
		if(result.numerator / result.denominator != 0) {
			printf(" ");
		}
		printf("%lld/%lld\n", result.numerator % result.denominator, result.denominator);
	}
	return 0;
}

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

digit add(digit d1, digit d2) {
	long long newDenominator = d1.denominator * d2.denominator;
	long long newNumerator = d1.numerator * d2.denominator + d2.numerator * d1.denominator;
	long long common = gcd(abs(newDenominator), abs(newNumerator));	//防止负数传进去 
	return digit(newNumerator / common, newDenominator / common);
}

C++解题报告：