登录
← 返回首页 | 代码片段 › 1 基础算法 › 1.2 GCD与LCM › GCD与LCM / 搜索
JSON MD

1.2 GCD与LCM

gcd 与 lcm gcd
6 行
CPP JSON
【最大公约数(GCD)与最小公倍数(LCM)】 ▪ gcd(a, b) — 辗转相除法(欧几里得算法):b==0 时返回 a,否则递归 gcd(b, a%b) ▪ lcm(a, b) — 最小公倍数:a / gcd(a,b) * b(先除后乘防止溢出) 时间复杂度 O(log min(a,b))。适用于约分、周期计算、分数通分等基础数论场景。
C++ 6 行 CPP
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
int lcm(int a,int b){
    return a * b / gcd(a,b);
}
已复制