确定x/y分数有重复小数展开

Question

有没有什么快速的方法可以根据最后给出结果重复部分的整数来确定 x/y 分数？谢谢。

def repeatless(x, y):
    // some code here...
    return True

Answer 1

给定整数 x 和 y，分数 x/y 具有重复小数展开当且仅当：

y / gcd(x, y) 有除 2 和 5 以外的因子，并且
x除以y的余数不为零

注意：正如评论中所指出的，我最初的回答有一个缺陷，即只有当 x/y 是不可约分数（最低限度）时它才有效。这可以通过首先将 y 除以 gcd(x, y) 来解决，这样您就可以检查等效不可约分数的分母是否具有 2 和 5 的幂以外的因子。

第二个条件很容易检查：

HasRepeatingDecimal(x, y)
1. if x % y == 0 then return false

现在我们需要看看 y / gcd(x, y) 是否有除 2 和 5 以外的因子。我们可以通过重复将 y / gcd(x, y) 除以 5 再除以 2 来做到这一点，看看如果我们以数字 1 结束：

HasRepeatingDecimal(x, y)
1. if x % y == 0 then return false
2. y = y / gcd(x, y)
3. while (y % 5 == 0) y = y / 5
4. while (y % 2 == 0) y = y / 2
5. if y == 1 then return true else return false

您可以检查分母是否能被 2 和 5 整除的原因是十进制系统以 10 为底，而 2 和 5 是 10 的唯一质因数。如果您使用的是 21 进制，则需要检查y / gcd(x, y) 改为 3^a x 7^b 的形式。

确定x/y分数有重复小数展开

Determine x/y fraction has repeating decimal expansion

math

fractions