一个特定字符串的排列数量可以被一个数字整除

Question

假设我有一个包含10个数字的多重集合，例如S = { 1, 1, 2, 2, 2, 3, 3, 3, 8, 9 }。除了暴力方法外，是否有其他方法可以找到S元素的不同排列数，使得当将排列视为一个十位数时，它可被特定数字n整除？n将在1到10000范围内。

例如：

如果S = { 1, 2, 3, 4, 6, 1, 2, 3, 4, 6 }且n = 10，则结果为0（因为这些10个数字的任何排列都不会得到可被10整除的数字）。

如果S = { 1, 1, 3, 3, 5, 5, 7, 7, 9, 2}且n = 2，则结果为9! / 2^4（因为我们必须在末尾放置2，有9!种方法可以对其他元素进行排列，但有四对相同的元素）。

- russell

---

不，这不是作业，因为我现在不是学生，只是为了学习新东西。 - russell

我不理解这个问题。您是在问一个回答“我的字母表中哪些字符串的唯一排列计数可被给定的有界NUM整除”的算法吗？还是“在将给定字符串视为整数时，哪些排列可以被给定的有界NUM整除？” - phs

这听起来非常像一个欧拉计划问题（www.projecteuler.net），但我在那里找不到它！:-) 我看不出这可以在不使用暴力的情况下完成。通常（但并不总是），找到“精确”的数字意味着要使用暴力方法。 - Jaco Van Niekerk

不是字母，只是数字0-9。将给定字符串的排列作为一个整数时，能被给定的数整除，该数可以是1到10000之间的任意数。 - russell

不需要知道相应的排列，只需要计算可被整除的排列数量即可。 - russell

Answer 1

你可以这样剪枝搜索：找到NUM的质因数分解。显然，为了能被NUM整除，一个排列需要被NUM的所有质因数整除。因此，你可以使用简单的整除规则来避免生成许多无效的候选项。

- mitchus

---

如何加速？它是否需要生成所有排列或检查所有质因数的倍数？ - russell

例如，如果2是NUM（显然已经更名为n）的一个质因数，那么您就知道任何有效的候选者必须具有偶数个末位数字。这意味着您可以避免生成和测试任何末位数字为奇数的排列；您已经知道它们不会被n整除。 - mitchus

作为另一个更极端的例子，如果3是一个质因数，那么你可以检查S中数字之和是否能够被3整除。如果不能被整除，那么你就不需要生成任何候选项：你已经知道没有解决方案。另一方面，如果总和是3的倍数，那么你可以确信任何排列都将满足该条件，然后你可以继续处理其他质因数。 - mitchus

Answer 2

我有一些想法，但还没有组织成实际的算法。

对于N=2，我们只需看看我们可以在排列末尾放置多少个偶数位数字，并通过计算得出数量。

对于N=3，我们知道数字的总和必须是3的倍数。这意味着我们可以自由地将任何3、6、9和0放入我们的排列中，但任何其他数字都必须成对放置，使其总和为3、6或9（或三个1）。我认为这不会太难实现。

对于N=4，我们可以类似于N=2的方式处理。

我认为我们可以为N=10以内的情况制定类似的方案（N=7可能有些棘手）。然后，我们可能可以通过分解来处理任何大于N=10的N。例如，如果N=18，则所有可被N整除的排列也可被2和9整除。当然，如果N是一个质数，我们可能会遇到麻烦。

- Colin

---

那这基本上就和我的回答一样了，对吧？ :) - mitchus

是的 :) 在我发布自己的答案之前，我没有仔细阅读你的答案，然后我抬头看到你基本上说了同样的话，但更简洁。然后我因为尴尬而关闭了选项卡。 - Colin

Answer 3

我的想法是：将S的数字按升序和降序排序。现在你有了可以从S生成的最小值和最大值。现在，在min和max区间内取所有N的倍数，看看它们中哪些由S中的数字组成。

- Tudor

---

这比普通的暴力破解还要糟糕，如果NUM是2，则在-1000000000-9999999999之间的倍数数量，你能想象！！！还没有完成，现在检查S中相应数字的计数，每个倍数里面还有一个循环！！ - russell

你说得没错，但我仍然坚持认为对于大的N值，你检查的数字比暴力方法要少得多。 - Tudor

对于大数值，可能更好，但对于我的问题，NUM是2-10000，因此需要一种可以处理这个范围内任何数字的方法。 - russell