题解 | #求最小公倍数#
求最小公倍数
https://www.nowcoder.com/practice/22948c2cad484e0291350abad86136c3
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
步骤：
- gcd(a, 0) 基准情况
- gcd(a, b) = gcd(b, a%b) 递归情况
