笔试训练48天:求最小公倍数

张开发
• 2026/4/5 1:38:18 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

笔试训练48天:求最小公倍数
描述对于给定的两个正整数 a,ba,b它们的最小公倍数 lcm⁡(a,b)lcm(a,b) 是指能同时被 aa 和 bb 整除的最小正整数。求解 lcm⁡(a,b)lcm(a,b)。输入描述在一行上输入两个整数 a,b(1≦a,b≦105)a,b(1≦a,b≦105)。输出描述输出一个整数表示 lcm⁡(a,b)lcm(a,b)。方法lcm(a,b)(axb)/gcd(a,b)gcd最大公约数方法辗转相除法辗转相除法欧几里得算法求最大公约数核心原理两个数的最大公约数 其中较小数 与 两数相除余数 的最大公约数直到余数为 0此时的除数就是最大公约数GCD。一、步骤用较大数 ÷ 较小数得到余数把原来的除数当作新被除数余数当作新除数重复相除直到余数 0最后一次的除数就是最大公约数二、举例求48 和 18的最大公约数48 ÷ 18 2 …… 1218 ÷ 12 1 …… 612 ÷ 6 2 …… 0余数为 0停止计算→最大公约数是 6#include iostream using namespace std; int gcd(int a,int b) { if(b0)return a; return gcd(b,a%b); } int main() { int a, b; cinab; cout(a*b/gcd(a,b))endl; return 0; }

更多文章