求解思路
这题的实质就是最大公约数gcd和最小公倍数lcm,但我发现不需要lcm也可以通过,那就先直接暴力,最后的结果再求一个最大公约数化简一下。
一点碎碎念
因为习惯性用C++,所以一开始用的C++的cin输入,完全没有考虑到可以用C里面的scanf,因为题目要求输入格式是固定的——int/int,所以用C里面的scanf会方便很多。改进前,输入字符串,再分割字符串,转换成相应的数值。(这么麻烦的我方法我居然写了orz。) 改进后,几行代码,发现自己好傻哈哈哈。
题目不难,但是好多小问题debug了好久,比如gcd和输出格式问题。
C++源码
#include<iostream>
#include<cstdio>
using namespace std;
long int gcd(long int a, long int b)
{
// assume that the input satisfies a > b
if(b < 0)
{
b = b * (-1);
}
long int r;
while(b != 0)
{
r = a % b;
a = b;
b = r;
}
return a;
}
int main()
{
int N;
long int up = 0, down = 1;
long int remainder, gcdVal = 0;
long int integer = 0, numerator = 0, denominator = 0;
cin>>N;
long int *a = new long int[N];
long int *b = new long int[N];
for(int i = 0; i < N; i++)
{
scanf("%lld/%lld", &a[i], &b[i]);
}
for(int i = 0; i < N; i++)
{
down *= b[i];
}
for(int i = 0; i < N; i++)
{
up += a[i] * (down / b[i]);
}
if(up == 0)
{
cout<<"0"<<endl;
return 0;
}
integer = up / down;
remainder = up % down;
if(remainder != 0)
{
gcdVal = gcd(down, remainder);
numerator = remainder / gcdVal;
denominator = down / gcdVal;
}
// output, pay attention to the format
if(integer != 0 && numerator != 0)
{
cout<<integer<<" "<<numerator<<"/"<<denominator;
}
else if(numerator == 0)
{
cout<<integer;
}
else if(integer == 0)
{
cout<<numerator<<"/"<<denominator;
}
cout<<endl;
return 0;
}
回顾gcd
int gcd(int a, int b)
{
int r;
a = abs(a);
b = abs(b);
// ensure that a > b
if(a < b)
{
int temp = b;
b = a;
a = temp;
}
while(b != 0)
{
r = a % b;
a = b;
b = r;
}
return a;
}
回顾lcm
int lcm(int a, int b)
{
return a / gcd(a, b) * b;
}