最大公约数gcd和最小公倍数lcm

// a>b; 但 不需要     若a>b则gcd(a,b)       a<b则gcd(b,a)
int gcd(int a,int b){
    if(b == 0)  return a;
    else return gcd(b,a%b);
}

其中d为a和b的最大公约数
最小公倍数 为ab/d 但是其有溢出的风险 所以应该改变下运算顺序 a/db 由于d是a和b的最大公约数 所以a/d 一定是可以整除的

1081 Rational Sum (20 分)
https://pintia.cn/problem-sets/994805342720868352/problems/994805386161274880

int a=0,b=1;
while(n--){
    int c,d;
    scanf("%d/%d",&c,&d);
    a = a*d+b*c;
    b = b*d;
    int t = gcd(a,b);
    a /= t; b/=t;
}
// 最终a与b就是分数求和的分子和分母 (numerator/denominator)
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容