1. 概括
这应该是最基础的知识，我估摸着甚至不会单独作为一道题出现在LeetCode里，但是我的的确确是不会了，所以这边记录一下相关算法，基本方法是求两个数的最大公约数（GCD）和最小公倍数（LCM）。
2. 方法和代码
2.1 质因数分解法
把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这几个数的最大公约数，把几个数先分别分解质因数，再把各数中的全部公有的质因数和独有的质因数提取出来连乘，所得的积就是这几个数的最小公倍数。
例如24和60，24=2×2×2×3，60=2×2×3×5，公共的质因数是2×2×3=12，也就是说最大公约数(24, 60)=12，除了公共的因数之外，24里剩余的独立因数是2，60里剩余的独立因数是5，与最大公约数的乘积是12×2×5=120，因此最小公倍数[24, 60]=120。
从代码来看，可以考虑枚举法和遍历质因数法，下面是枚举法：
def lcm(a, b):
for i in range(min(a,b),0,-1):
if a % i ==0 and b % i == 0:
return a*b//i
num1 = int(input(""))
num2 = int(input(""))
print(lcm(num1, num2))
思路是最大公约数最大也不会超过两者之间更小的那个数，然后从二者中更小的数开始向下便利，每次减1，直到找到两个都能整除的 i 就是最大公约数，而 a // i 和 b // i 就是各自剩余的独立因数 (a // i) * (b // i) * i = a * b // i 就是最小公倍数了。
下面是质因数分解法：
def lcm(a, b):
"""质因数分解"""
p = 1
i = 2
while i <= min(a, b):
if a % i == 0 and b % i == 0:
p *= i
a, b = a // i, b // i
else:
i += 1
p = p * a * b
return p
print(lcm(45, 30))
# 若是计算多个数的最小公倍数
a = [12, 30, 50]
s = a[0]
for i in a:
s = lcm(s, i)
print(s)
思路是从最小的质因数 i = 2 开始分解，p 用来累积质因数的积，每次分解成功的条件是 a 和 b 都要能够整除 i ，分解的过程是将 a 和 b 都整除 i 。因为是从最小的质因数开始尝试的，如果某一次分解条件不满足意味着这个质因数已经无法进一步分解这两个数了，就将 i 递增 1 来枚举后面可能存在的质因数，不需要担心递增 i 的过程中可能出现合数，因为合数可以被分解成比其小的质因数，这些质因数都已经被检查过了，所以遍历到合数的时候一定不能分解成功，会直接跳过。这样操作直到遍历的质因数已经比两个数都小了就到达分解边界了，因为再继续枚举也无法分解成功，此时累积的 p 就是最大公约数了，相应的用 p 乘上剩余的 a 和 b 就可以得到最大公倍数。
2.2 辗转相除法
原理是两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数，所以可以递归地将原问题变成子问题，gcd(a, b) = gcd(b, c)，其中a>=b，c = a % b。递归边界是c=0，此时a是b的倍数，所以最大公约数就是b了。
def gcd(a, b):
while a != 0:
a, b = b % a, a
return b
辗转相除法的时间复杂度不好计算，可以近似认为是O(log(max(a, b)))，缺点在于取模的运算对于计算机里说性能不佳。
2.3 更相减损法
设a和b的公约数为v，其中a>b，令a=vm，b=vn，那么有a-b=v(m-n)，也就是说a和b以及a-b两两之间的公约数也会是另一个数的约数，那么a和b的最大公约数x也会是b和a-b的最大公约数，如果不是，也就是说b和a-b还有比x大的公约数y，而y也会是a和b的公约数，出现了a和b的最大公约数比一个其中一个公约数小的矛盾。其实这个原理和辗转相除法是一样的，只不过从取模的运算变成了相减，递归方式为gcd(a, b) = gcd(a-b, b)，当然，这里要注意将大的数放在前面。
在此方法下可以与位运算结合做优化。考虑a=vm和b=vn，这里v=gcd(a, b)，也就是m和n互质。分类讨论，如果a和b都是偶数，会发现gcd(a>>1, b>>1)=v>>1，所以gcd(a, b) = v = 2gcd(a>>1, b>>1)；如果a是偶数而b是奇数，那么v中一定不包含2这个质因数否则会让b变成偶数，所以m里包含2，因此a>>1=v(m>>1)，gcd(a, b) = v = gcd(b, a>>1)；如果a是奇数而b是偶数，类似地有gcd(a, b) = v = gcd(a, b>>1)；如果a和b都是奇数，那么a-b就是偶数了，加上gcd(a, b) = gcd(a-b, b)，就可以转化前面的情况。
更相减损法虽然优化了辗转相除法里的取模运算性能，变成了性能优异的减法，但是最坏的运算情况时间复杂度为O(max(a, b))，而我们使用移位的分类讨论方式优化之后可以变成O(log(max(a, b)))，不仅时间复杂度优秀了，运算的性能也是优秀的。
3. 拓展
如果问题变成求多个数的最大公约数，那么就考虑拆成两两求最大公约数的子问题递归求解，比如gcd(a, b, c) = gcd(gcd(a, b), c)，甚至进一步可以考虑分治的思想，比如gcd(a, b, c, d) = gcd(gcd(a, b), gcd(c, d))，至于这个递归表达式的证明其实联系质因数分解不难得出。
为什么会突然总结最大公约数和最小公倍数，其实是因为一道LeetCode的题目，其中一个题解需要求最小公倍数，可以参照官方题解的189. 轮转数组-方法二：环状替换
