1081.md

1081

• 1081 Rational Sum (20 point(s))
• 分数加法

#include <iostream>
using namespace std;
typedef long long ll;

int N;
const int MAX_N = 100 + 5;
struct Fraction {
	ll up, down;
};

ll gcd(ll a, ll b) {
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}

void reduction(Fraction &r) {
	if (r.down < 0) {
		r.up = -r.up;
		r.down = -r.down;
	}
	if (r.up == 0) {
		r.down = 1;
	}
	else {
		ll d = gcd(abs(r.up), abs(r.down));
		r.up /= d;
		r.down /= d;
	}
}

Fraction add(Fraction f1, Fraction f2) {
	Fraction res;
	res.up = f1.up * f2.down + f1.down * f2.up;
	res.down = f1.down * f2.down;
	reduction(res);
	return res;
}

void print(Fraction f) {
	reduction(f);
	if (f.down == 1) {
		cout << f.up << endl;
	}
	else if (abs(f.up)>f.down) {
		cout << f.up / f.down << " " << abs(f.up) % f.down << "/" << f.down << endl;
	}
	else {
		cout << f.up << "/" << f.down << endl;
	}
}

int main() {
	Fraction sum, f;
	sum.up = 0;
	sum.down = 1;
	cin >> N;
	for (int n = 0; n < N; n++) {
		cin >> f.up;
		getchar();
		cin >> f.down;
		reduction(f);
		// cout << f.up << "/" << f.down << endl;
		sum = add(sum, f);
	}
	print(sum);
}

/*
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
*/

References

• 算法笔记