HJ108 求最小公倍数

描述

正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。

数据范围：

1 ≤ a , b ≤ 100000 1≤a,b≤1000001≤a,b≤100000

1≤a,b≤100000

输入描述：

输入两个正整数A和B。

输出描述：

输出A和B的最小公倍数。

示例1

输入：

5 7

输出：

35

示例2

输入：

2 4

输出：

4

思路

辗转相除法原理：

两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

例如：

欲求252和105的最大公约数；因为

252÷105=2…42，所以这个最大公约数也是42与105的最大公约数(42=21×2)。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至余数为零。这时，所剩下的还没有变成零的数就是两数的最大公约数。

我们将上述过程翻译成递归代码，得到如下函数：

def gcd(x,y):
    if x>y:
        x,y = y,x
    if x==0:return y
    return gcd(y%x,x)

注意本题要求是最大公倍数，根据数学定理，

a 与 b 的最大公倍数 = ( a ∗ b ) / / a 与 b 的最大公约数 a与b的最大公倍数 =(a*b)//a与b的最大公约数a与b的最大公倍数=(a∗b)//a与b的最大公约数

可直接得出答案

代码

a,b = map(int,input().split(" "))
def gcd(x,y):
    if x>y:
        x,y = y,x
    if x==0:return y
    return gcd(y%x,x)
print( (a*b)// gcd(a,b))