0

我正在使用公式“两个数字的乘积等于它们的 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

谁能告诉我我哪里出错了？

4

1 回答 1

5

对评论进行详细说明。在 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 之前的版本。

于 2016-08-20T13:20:15.150 回答