gcd与lcm

gcd

使用辗转相除法解决最大公因数
72/45=1……27
45/27=1……18
27/18=1……9
18%9==0
即最大公因数为9

int gcd(int a,int b){
    if(a%b==0){
        return b;
    }
    return gcd(b,a%b);
}

lcm

由于x,y的最大公因数乘以其最小公倍数等于xy,所以lcm(x,y)=xy/gcd(x,y);

int lcm(int a,int b){
     return a/gcd(a,b)*b;//由于a*b可能会爆int,所以先除后乘
}

本文链接:https://kaispace.com.cn/index.php/archives/286/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者