PAT A1081 Rational Sum (20分)

前言

传送门

正文

参考题解

#include<iostream>
#include<cmath>
using namespace std;
/* 题意： 给定n个有理数（以分数形式表示），计算这n个有理数的和 思路：涉及到分数运算，直接用算法笔记的分数四则运算模板即可。 分数运算设计到三个主要函数，一是求最大公约数，二是化简函数reduction， 三是输出函数showRes（一般输出形式是 整数部分+真分数部分） */
typedef long long LL;
struct Fraction{
	LL up,down;
}; 
//求最大公约数 
LL gcd(LL a,LL b){
	return b==0?a:gcd(b,a%b);
} 
//化简函数 
Fraction reduction(Fraction res){
	if(res.down<0){//分母为负数，则分子分母均为其相反数 
		res.up=-res.up;
		res.down=-res.down;
	}
	if(res.up==0){//分子为0 
		res.down=1;
	}else{//分子不为0，约分 
		LL factor=gcd(abs(res.up),res.down);
		res.up/=factor;
		res.down/=factor; 
	}
	return res; 
}

void showRes(Fraction res){
	res=reduction(res);
	if(res.down==1){//整数 
		printf("%lld\n",res.up);
	}else if(abs(res.up)>res.down){//假分数
		printf("%lld %lld/%lld\n",res.up/res.down,abs(res.up)%res.down,res.down); 
	}else {//真分数 
		printf("%lld/%lld\n",res.up,res.down);
	}
		
}
Fraction add(Fraction a,Fraction b){
	Fraction res;
	res.up=a.up*b.down+a.down*b.up;
	res.down=a.down*b.down;
	return reduction(res);//每次加法后都得对结果进行化简 
} 
int main(){
	int n;
	cin>>n;
	Fraction sum,temp;
	sum.up=0,sum.down=1;
	while(n--){
		scanf("%lld/%lld",&temp.up,&temp.down);
		sum=add(sum,temp); 
	} 
	showRes(sum);
	return 0;
}