题解 | #求最小公倍数#

def gcd(x, y):  # 辗转相除法求最大公约数
    if y == 0:
        return x
    else:
        return gcd(y, x%y)

def lcm(x, y):  # 用最大公约数求最小公倍数
    return x * y // gcd(x, y)

while True:
    try:
        A, B = map(int, input().split())
        print(lcm(A, B))
    except:
        break

• Least Common Multiple (LCM) 最小公倍数
• Greatest Common Divisor (GCD) 最大公约数

辗转相除法的关键在于：对gcd(a,b)而言，a%b后仍有gcd(b, 余数)=gcd(a,b)

例：a = 16, b = 10

16 / 10： 商 = 1，余数 = 6

有gcd(16, 10) = gcd(10, 6)。因为任何能同时整除16或10的公约数同时也能整除10和6（6本身是16 / 10的余数）

这样逐渐递归

gcd(16, 10)
= gcd(10, 6) 
= gcd(6, 4)
= gcd(4, 2)
= gcd(2, 0) 
= 2

得到gcd(2, 0)得到最大公约数2

步骤：

1. gcd(a, 0) 基准情况
2. gcd(a, b) = gcd(b, a%b) 递归情况