algorithm - 特定字符串的排列数可被数字整除

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! 方法来排列其他元素，但是有四对相同的元素)

Answer 1

您可以像这样修剪搜索:找到 NUM 的质因数分解。显然要被 NUM 整除，排列需要被 NUM 的所有素因子整除。因此你可以使用 simple divisibility rules 以避免产生许多无效候选。