【算法】gcd 和 lcm

张开发
• 2026/4/10 19:40:41 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【算法】gcd 和 lcm
【约数和倍数】如果 a 除以 b 没有余数余数为 0那么 a 就是 b 的倍数 b 就是 a 的约数记作 b ∣ a 。约数也称因数。求两个数的最大公约数Greatest Common DivisorGCDB4025 最大公约数 - 洛谷辗转相除法欧几里得算法原理若 a 和 b 是两个整数a b则 gcd(a, b) gcd(b, a % b)重复这个过程直到余数为 0。步骤较大数除以较小数得到余数。用较小数替换较大数余数替换较小数。重复 12 直到余数为 0此时的除数就是最大公约数。// 参数不必一定 x y,如果 x y,gcd(x,y) 一次后变成 gcd(y,x) int gcd(int x, int y) { return y 0 ? x : gcd(y, x % y); }时间复杂度求 gcd(a, b) 会遇到两种情况1. a b 则 gcd(a, b) gcd(b, a)2. a b 则 gcd(a, b) gcd(b, a mod b)第⼆种情况会让 a ⾄少折半因此最多执⾏ log n 次。第⼀种情况不会多于第⼆种因此时间复杂度为 O(log n) 。求三个数的最大公约数可以使用以下方法利用公式gcd(a,b,c) gcd(gcd(a,b),c)步骤先求前两个数的最大公约数再求这个结果与第三个数的最大公约数求两个数的最小公倍数(Least Common Multiple,LCM)B3634 最大公约数和最小公倍数 - 洛谷对于两个数 a 和 b 。gcd(a, b) × lcm(a, b) a × b也就是最⼤公约数乘以最⼩公倍数等于两个数的乘积。因此⼀般先求最⼤公约数然后⽤这个性质求最⼩公倍数。int lcm(int x, int y) { return x / gcd(x, y) * y; // 注意防止溢出 }求三个数的最小公倍数可以使用以下方法利用公式lcm(a,b,c) lcm(lcm(a,b),c)步骤先求前两个数的最小公倍数再求这个结果与第三个数的最小公倍数

更多文章