the problem is from PAT,which website is http://pat.zju.edu.cn/contests/pat-a-practise/1081
the code is as followed:
#include<stdio.h>
#include<math.h>
long int gongyue(long int num1, long int num2)
{
long int gcd=0;
if (num1==num2)
{
gcd = num1;
}
if (num1>num2)
{
long int tmp = num1;
num1 = num2;
num2 = tmp;
}
if (num2 % num1 == 0)
{
gcd = num1;
}
else
{
long int tmp = num1;
num1 = num2 % num1;
num2 = tmp;
gcd = gongyue(num1, num2);
}
return gcd;
}
long int gongbei(long int x, long int y)
{
return x * y / gongyue(x,y);
} int main()
{
long int fenzi,fenmu;
long int tempzi,tempmu;
int n;
//printf("%d",gongbei(3,8));
scanf("%d",&n);
scanf("%ld/%ld",&fenzi,&fenmu);
n -= 1;
long int temp = fenzi;
if (fenzi == 0)
{
fenmu = 1;
}
else
{
fenzi = fenzi / gongyue(abs(temp), fenmu);
fenmu = fenmu / gongyue(abs(temp), fenmu);
}
while (n--)
{ scanf("%ld/%ld",&tempzi,&tempmu);
fenzi = fenzi * gongbei(fenmu,tempmu)/fenmu + tempzi * gongbei(fenmu,tempmu)/tempmu;
fenmu = gongbei(fenmu,tempmu);
long int tempfenzi = fenzi;
if (fenzi == 0)
{
fenmu = 1;
}
else
{
fenzi = fenzi / gongyue(abs(tempfenzi), fenmu);
fenmu = fenmu / gongyue(abs(tempfenzi), fenmu);
} }
if (abs(fenzi)>=fenmu)
{
printf("%ld",fenzi/fenmu);
if (fenzi%fenmu != 0)
{
printf(" %ld/%ld",abs(fenzi)%fenmu,fenmu);
}
printf("\n");
}
else
{
if (fenzi == 0)
{
printf("0");
}
else
{
printf("%ld/%ld",fenzi,fenmu);
}
printf("\n");
}
}
the time complexity is O(n) .