给定 x 和 y，如何判断 x! 是否能被 y 整除？

Question

计算x!可能非常昂贵，而且往往会导致溢出。有没有一种方法可以在不计算x!的情况下找出它是否可被y整除呢？

• 对于y<x，这是微不足道的；
• 但是，对于y>x，例如x=5和y=60；我正在努力寻找一种方法，而不需要计算x！

- Ritesh Mahato

---

y 和 x 相比如何？如果 y<=x，那么 y 肯定能整除 x!。如果 y 是质数且 y>x，那么它不能整除，但是如果 y>x 且它的所有质因数都 <=x，那么也许可以... 在这种情况下，您可以通过生成 2..x 的所有因子列表，然后确保 y 的因子是该列表的子集来解决它... - twalberg

你可以尝试在http://math.stackexchange.com/上提问。 - sinelaw

这基本上是一个数学定义/简单算法问题 - 提到“质因数分解”几乎是太危险的提示，因为你可以通过查找来作弊。 - clwhisk

@clwhisk 这完全取决于数字 x 和 y 的规模。 - Niklas B.

@NiklasB。但是找到y的质因数分解或多或少地解决了问题，而且似乎是最小量的工作。 - clwhisk

Answer 1

计算x!和y的质因数分解。你可以通过对2到x中的每个数字进行因式分解并将所有因子收集在一起来完成此操作，而无需计算x!。如果y的因子是x!的因子的子集，则x!可被y整除。

- IronMensan

---

实际上，您甚至不需要分解x！假设我想知道2^17是否可以整除20！我知道2、4、6、8...每个数字都会对质因数分解贡献一个2。然后4、8、12、16每个数字再贡献一个2，以此类推，总共为2^(20/2 + 20/4 + 20/8 + 20/16) = 2^18。同样地，它还有3^(20/3 + 20/9) = 3^8作为因子。 - Russell Zahniser

对于给定的例子，60的质因数分解是2^2 * 3 * 5。5!的质因数分解为2^(5/2 + 5/4) = 2^3，所以这个因子是正确的。它还有3^(5/3) = 3^1和5^(5/5) = 5^1。 - Russell Zahniser

使用NlogN排序和线性集合交集，O(x^1.5 + y^1.5 + sqrt(x)log(x) + sqrt(y)log(y))。 - Ralor

Answer 2

如果x和y都非常大，不可行通过迭代1到x的所有数字来计算。相反，您可以对y进行因式分解，并计算每个质因数的最大幂是否也能够被x!整除。

我已经更详细地介绍了该算法在另一个答案中（链接）。

基本上，检查过程如下：

// computes maximum q so that p^q divides n!
bool max_power_of_p_in_fac(int p, int n) { 
    int mu = 0;
    while (n/p > 0) {
        mu += n/p;
        n /= p;
    }
    return mu;
}
// checks whether y divides x!
bool y_divides_x_fac(int y, int x) {
    for each prime factor p^q of y:
        if (max_power_of_p_in_fac(p, x) < q)
            return false;
    return true;
}

这导致了一个算法，对于 x < y 的情况，其复杂度为 O(分解 y 的时间 + log x * y 的质因数个数)。

显然，y 可以有 O(log y) 个质因数。因此，使用波拉德-罗（Pollard's rho）分解，这将类似于 O(y^(1/4) + log x * log y)。

可以使用这个定理证明其正确性：

- Niklas B.

---

质因数的个数~对数对数y？ - Ralor

@Ralor 应该是“不同质因数的数量”。log log y 只是一个粗略的估计，但是 primorials（随着 y 的增长非常快） grow very fast。 - Niklas B.

@Nicklas B. 嗯，好的。我使用了O(sqrt(y))分解算法会在所有小于等于sqrt(y)的奇数上找到质数的事实，所以我的上限可能不是很好。当然，log(y)更好。 - Ralor

@NiklasB。在您的函数'pq_divides_x_fac'中，'n'是什么？ - Ritesh Mahato

@NiklasB，非常棒的解决方案。谢谢！ - Ritesh Mahato

Answer 3

对于从 1 到 x 的每个数字 i，执行操作 y /= gcd(y, i)。最后进行整除检查，判断 y == 1 是否成立。

- David Eisenstat

---

那很有趣！O(xlog(y)) - Ralor