P4737 童童的分数计算（基础）

解题思路

输入 n 个分数，形式是"a/b"，分子分母都是正整数。要求把这 n 个分数加起来，结果用最简分数表示。所谓最简分数，就是分子和分母的最大公约数为 1；如果约分后分母变成 1，就直接输出一个整数。

分数相加不能直接把分子加起来，必须先把分母统一，也就是"通分"。我们求出所有分母的最小公倍数 L，把每个分数都改写成分母为 L 的分数：a/b 就变成 a×(L÷b) 再除以 L。这样所有分数分母相同了，直接把分子相加就得到结果的分子，分母就是 L。最后用辗转相除法求出分子、分母的最大公约数 g，分子分母同除以 g 就化简成最简分数了。如果约分后分母为 1，直接输出分子；否则输出"分子/分母"的形式。

举个例子：1/5 + 1/6 + 1/3。三个分母 5、6、3 的最小公倍数是 30，通分后变成 6/30 + 5/30 + 10/30 = 21/30，分子分母同除以最大公约数 3，得到 7/10。这道题 n 最大 10，每个分母不超过 10，所以最小公倍数最大只有 2520，分子之和也不会超过 252000，用 long long 保存绝对安全。注意读入时用 scanf 的"%d/%d"格式直接读"a/b"。

参考代码

// 童童的分数计算：n个分数求和，用最简分数输出，分母为1时直接输出整数
#include <cstdio>
long long gcd(long long a,long long b){  // 辗转相除法求最大公约数
  long long t;
  while(b){ t=a%b; a=b; b=t; }
  return a;
}
int main(){
  int n,i,aa[15],bb[15];
  long long L=1,num=0,den,g;
  std::scanf("%d",&n);
  for(i=0;i<n;i++){
    std::scanf("%d/%d",&aa[i],&bb[i]);
    L=L/gcd(L,bb[i])*bb[i];              // 边读边求所有分母的最小公倍数L
  }
  for(i=0;i<n;i++) num+=(long long)aa[i]*(L/bb[i]);  // 通分后分子相加
  den=L;
  g=gcd(num,den);                        // 分子分母同除以最大公约数化简
  num/=g; den/=g;
  if(den==1) std::printf("%lld\n",num);  // 分母为1直接输出整数
  else std::printf("%lld/%lld\n",num,den);
  return 0;
}

复杂度分析

先扫一遍所有分数求最小公倍数，再扫一遍求和，最后做一次辗转相除法，总共 O(n) 次运算，其中 gcd 每次是 O(log) 级别，n 又很小，所以非常快。空间上用两个小数组存放分子分母，是 O(n)。