Easy LCM Problem

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 4 总提交人数: 4

题目描述

在数论中,约数与倍数是很常见的概念。若有一个正整数 $x$ 可以被另外两个正整数 $a, b$ 整除,则 $x$ 为 $a, b$ 的公倍数,其中最小的公倍数叫做最小公倍数(LCM, Least Common Multiple),记为 $\mathrm{lcm}(a, b)$。

现在给定 $a, b$,请你求出 $\mathrm{lcm}(a, b)$ 的值。

输入格式

输入一行两个用空格隔开的正整数 $a, b$($1 \leq a, b \leq 1,000$)。

输出格式

输出一行一个整数 $\mathrm{lcm}(a, b)$。

样例输入1

12 8

样例输出1

24

样例输入2

299 943

样例输出2

12259

提示1

还记得课件中计算两个正整数的最大公约数(GCD, Greatest Common Divisor)的方法吗?如何直接改造课件中的程序,使得计算的东西变成最小公倍数?

提示2

如果你不想改造程序,也可以利用下面的性质:

$$\mathrm{gcd}(a, b) \times \mathrm{lcm}(a, b) = a \times b$$

其中 $\mathrm{gcd}(a, b)$ 表示 $a, b$ 的最大公约数。用这个方法,课件里的代码就成为本方法的一个组成部分。

思考

采用提示1和提示2的方法,哪种方法更有效?为什么?

AUTHOR:廖纪童

相关推荐