超级码力初赛第三场 最大公倍数
目录
题目描述
小栖有一个区间[a,b],他准备从中取三个数,他想知道如何取才能使得它们的最小公倍数最大 请直接告诉小栖最小公倍数是多少。
1<=a<b<=5000 b-a >= 2
示例
-
示例 1:
1 2 3 4
输入: a = 3, b = 6 输出: 60 样例解释: 4,5,6的最小公倍数是60
来源:九章算法
-
解题思路
每三个数为一组, 算出三个数的最小公倍数,加入到数组排序, 选出最大即可。
暴力枚举要避免超时。
-
题解1:
执行用时:56
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
class Solution: """ @param a: Left margin @param b: Right margin @return: return the greatest common multiple """ def greatestcommonmultiple(self, a, b): # write your code here def get_max_yinshu(x, y): while (True): if (x < y): x, y = y, x if (x % y == 0): return int(y) else: temp = x % y x = y y = temp tmp = [] aim = list(range(a, b + 1)) # 避免超时 if len(aim) > 6: aim = aim[-1:-6:-1] for x in range(len(aim)): for y in range(len(aim)): for z in range(len(aim)): a = aim[x] b = aim[y] c = aim[z] if a != b != c: if a<b<c: a_b = get_max_yinshu(a, b) a_b = int((a * b) / a_b) result = get_max_yinshu(a_b, c) result = int((a_b * c) / result) tmp.append(result) tmp.sort() return tmp[-1]