python中大数的LCM

Question

我使用的公式是“两个数的乘积等于它们的 GCD 和 LCM 的乘积”。

这是我的代码：

# Uses python3

import sys

def hcf(x, y):

    while(y):
        x, y = y, x % y

    return x

a,b = map(int,sys.stdin.readline().split())

res=int(((a*b)/hcf(a,b)))
print(res)

它适用于小数字。但是当我输入时：

输入：226553150 1023473145

我的输出：46374212988031352

正确输出：46374212988031350

谁能告诉我我哪里错了？

Answer 1

详细说明评论。在 Python 3 中，真正的除法/, 将其参数转换为浮点数。在您的示例中， 的真正答案lcm(226553150, 1023473145)是46374212988031350。通过查看bin(46374212988031350)您可以验证这是一个 56 位数字。当您计算226553150*1023473145/5（5 是 gcd）时，您会得到4.637421298803135e+16. 文档表明这种浮点数只有 53 位的精度。由于 53 < 56，您丢失了信息。使用//可以避免这种情况。有点违反直觉，在这种情况下，“真”除法实际上是错误的。

顺便说一句，在处理涉及大整数的精确计算时，一个有用的模块是分数(*)：

from fractions import gcd
def lcm(a,b):
    return a*b // gcd(a,b)

>>> lcm(226553150,1023473145)
46374212988031350

(*) 我只是注意到文档上fractions说它是这样的gcd：“自 3.5 版起已弃用：改用 math.gcd()”，但我决定保留fractions对它的引用，因为了解它仍然很好，你可能会使用 3.5 之前的版本。