Posts pythonTip 18 逆解最大公约数与最小公倍数
Post
Cancel

pythonTip 18 逆解最大公约数与最小公倍数

题目描述:

我们经常遇到的问题是给你两个数,要你求最大公约数和最小公倍数。今天我们反其道而行之,给你两个数a和b,计算出它们分别是哪两个数的最大公约数和最小公倍数。输出这两个数,小的在前,大的在后,以空格隔开。若有多组解,输出它们之和最小的那组。注:所给数据都有解,不用考虑无解的情况.

分析

江湖规矩: “如果暴力不能解决问题,再想想其他的解决办法。”

我先根据这两个数的大小,把这两个数给安排一下。保证 a < b

最小公倍数 和 最大公约数的转换,我是知道的。

最小公倍数 = a * b / gcd(a, b)

那么最小公倍 最大也只可能是 a * b, 最小 也是 b

所以,嘿嘿,嘿嘿。 从 b 遍历 到 a * b。 满足条件就退出。

from math import gcd

c, d = min(a, b), max(a, b)

a, b = c, d

# print(a, b)

ab = a * b

for i in range(1, ab+1):
    if b % i == 0:
        c, d = i, ab//i
        if d < c:
            break
        # print(c, d, gcd(c, d))

        if gcd(c, d) == a and c*d // gcd(c, d) == b:
            res_c, res_d = c, d

print(res_c, res_d)
This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 17 公约数的个数

pythonTip 19 单身情歌

Trending Tags