Coding Problem about Least Common Multiple and Greatest Common Divisor

发表 分类 阅读量: Valine: 字数: 1.1k 阅读时长 ≈ 1 分钟

在复习期末考试，被计算最小公倍数的一道题卡了两次了……怪我数学基础忘光了。在此整理一下最小公倍数和最大公约数相关的概念和定理。然后整理一下这道题：

Write a function to take in a tuple of integers, and it will return the smallest integer that is a multiple of every number in the tuple. Sample run:

>>> print(smallestMultiple((2, 3, 5,)))

30

>>> print(smallestMultiple((1, 2, 3, 4)))

12

>>> print(smallestMultiple((399, 772, 163, 959, 242)))

832307365428

概念和定理

最大公约数：如果一个数可以分别被a和b整除，那它就是a和b的公约数。最大的那个就是最大公约数。

最小公倍数：如果一个数既是a的整数倍，也是b的整数倍，那它就是a和b的公倍数。最小的那个就是最小公倍数。

辗转相除法：一个计算最大公约数的方法，如下：

辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。例如，252和105的最大公约数是21（\({\displaystyle 252=21\times 12;105=21\times 5}\) ）；因为 252 − 105 = 21 × (12 − 5) = 147 ，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至余数为零。这时，所剩下的还没有变成零的数就是两数的最大公约数。

利用GCD直接计算LCM：任何两个整数的最大公约数与最小公倍数存在如下关系： \[ LCM(a, b) = |a * b| / GCD(a, b) \]

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def smallestMultiple(tp):
    def GCD(a, b):
        while b > 0: # need a>b
            a, b = b, a%b
        return a
    res = 1
    for i in tp:
        a, b = max(res, i), min(res, i)
        res = abs(res * i) / GCD(a, b)
    return int(res)

print(smallestMultiple((2, 3, 5,)))
print(smallestMultiple((1, 2, 3, 4)))
print(smallestMultiple((399, 772, 163, 959, 242)))