我们应该使用什么算法来获得 n 位数字的计数，使得其数字的乘积为 p；这里的特殊条件是没有一个数字应该是 1；
到目前为止我的想法是对 p 进行素数分解。假设 n=3 和 p=24。
我们首先对 24 进行素数分解，得到：2*2*2*3。
现在我在确定这些组合时遇到问题
4*2*3 , 2*4*3, .... 等即使可以这样做...我将如何缩放 n 远小于素数。
我不太确定这是否是正确的方向......欢迎任何意见。
问问题
2925 次
6 回答
5
首先，你真的不需要完整的素数分解，只需要分解成小于你的基数的素数（我猜你的意思是 10，但这个问题可以推广到任何基数）。所以我们只需要分解成前 4 个素数：2、3、5 和 7。如果其余（素数或非素数）因子大于 1，则问题有 0 个解。
现在，让我们假设这个数字p被分解为：
p = 2^d1 * 3^d2 * 5^d3 * 7^d4
并且也由n数字组成：
p =d (n-1) d (n-2) ...d 2 d 1 d 0
然后，重新排列数字，也将是：
p = 2^q2 * 3^q3 * 4^q4 * 5^q3 * ... * 9^q9
在哪里qi >= 0和q2 + q3 + ... q9 = n
还有（由于分解）：
for prime=2: d1 = q2 + 2*q4 + q6 + 3*q8
for prime=3: d2 = q3 + q6 + 2*q9
for prime=5: d3 = q5
for prime=7: d4 = q7
所以q5andq7是固定的，我们必须找到方程的所有非负整数解：（
其中未知数是其余的qi：）q2, q3, q4, q6, q8 and q9
d1 = q2 + 2*q4 + q6 + 3*q8
d2 = q3 + q6 + 2*q9
n - d3 - d4 = q2 + q3 + q4 + q6 + q8 + q9
对于上述每一种解决方案，都有数位重排，可以通过以下公式求出：
X = n! / ( q2! * q3! * ... q9! )
必须总结一下。
可能有一个封闭的公式，使用生成函数，您可以将其发布在 Math.SE
p=24,的示例n=3：
p = 2^3 * 3^1 * 5^0 * 7^0
我们有：
d1=3, d2=1, d3=0, d4=0
整数解：
3 = q2 + 2*q4 + q6 + 3*q8
1 = q3 + q6 + 2*q9
3 = q2 + q3 + q4 + q6 + q8 + q9
是(q2, q3, q4, q6, q8, q9) =：
(2, 0, 0, 1, 0, 0)
(1, 1, 1, 0, 0, 0)
这给了：
3! / ( 2! * 1! ) = 3
3! / ( 1! * 1! * 1! ) = 6
和 3+6 = 9整体解决方案。
p=3628800,的示例n=10：
p = 2^8 * 3^4 * 5^1 * 7^1
我们有：
d1=8, d2=4, d3=1, d4=1
整数解：
8 = q2 + 2*q4 + q6 + 3*q8
4 = q3 + q6 + 2*q9
8 = q2 + q3 + q4 + q6 + q8 + q9
是(q2, q3, q4, q6, q8, q9)（连同相应的数字和每个解决方案的重新排列）：
(5, 0, 0, 0, 1, 2) 22222899 57 10! / (5! 2!) = 15120
(4, 0, 2, 0, 0, 2) 22224499 57 10! / (4! 2! 2!) = 37800
(4, 1, 0, 1, 1, 1) 22223689 57 10! / (4!) = 151200
(3, 2, 1, 0, 1, 1) 22233489 57 10! / (3! 2!) = 302400
(4, 0, 1, 2, 0, 1) 22224669 57 10! / (4! 2!) = 75600
(3, 1, 2, 1, 0, 1) 22234469 57 10! / (3! 2!) = 302400
(2, 2, 3, 0, 0, 1) 22334449 57 10! / (3! 2! 2!) = 151200
(2, 4, 0, 0, 2, 0) 22333388 57 10! / (4! 2! 2!) = 37800
(3, 2, 0, 2, 1, 0) 22233668 57 10! / (3! 2! 2!) = 151200
(2, 3, 1, 1, 1, 0) 22333468 57 10! / (3! 2!) = 302400
(1, 4, 2, 0, 1, 0) 23333448 57 10! / (4! 2!) = 75600
(4, 0, 0, 4, 0, 0) 22226666 57 10! / (4! 4!) = 6300
(3, 1, 1, 3, 0, 0) 22234666 57 10! / (3! 3!) = 100800
(2, 2, 2, 2, 0, 0) 22334466 57 10! / (2! 2! 2! 2!) = 226800
(1, 3, 3, 1, 0, 0) 23334446 57 10! / (3! 3!) = 100800
(0, 4, 4, 0, 0, 0) 33334444 57 10! / (4! 4!) = 6300
这是2043720完整的解决方案，如果我没有犯任何错误的话..
于 2013-01-07T11:08:54.193 回答
3
我不认为我会从解决已知的“困难”问题开始，即计算素数分解。我不认为我的意思是我的直觉，而不是对复杂性的任何严格计算，告诉我。
由于您最终只对pI 的个位数除数感兴趣，因此首先除以p，2然后除以3，然后4一直到9。当然，其中一些除法不会产生整数结果，在这种情况下，您可以放弃该数字，不再考虑。
对于你的例子，p = 24你会得到{{2},12}, {{3},8}, {{4},6}, {{6},4}, {{8},3}（即除数和余数的元组）。现在再次应用该方法，尽管这次您正在寻找其数字乘以余数的 2 位数字。也就是说，因为{{2},12}你会得到{{2,2},6},{{2,3},4},{{2,4},3},{{2,6},2}. 碰巧所有这些结果都提供了 3 位数字，其数字乘以24，但一般来说，一些余数可能仍然有 2 位或更多位，您需要在这些点修剪搜索树。现在回去{{3},8}继续。
请注意，这种方法避免了必须单独计算需要考虑的一组数字的多少排列，因为它枚举了所有排列。它还避免了必须考虑2*2和4作为单独的候选者。
我希望您也可以通过一些记忆来加快速度。
现在我期待有更多组合学知识的人告诉我们这个问题的封闭式解决方案。
于 2013-01-07T09:57:35.160 回答
3
您可以使用基于以下公式的动态编程方法：
f[ n ][ p ] = 9 * ( 10^(n-1) - 9^(n-1) ), if p = 0
0, if n = 1 and p >= 10
1, if n = 1 and p < 10
sum{ f[ n - 1 ][ p / k ] for 0 < k < 10, p mod k = 0 }, if n > 1
第一种情况是 p = 0 的单独情况。这种情况在 O(1) 中计算，此外有助于从第 4 种情况中排除 k = 0 值。
第二种和第三种情况是动态基础。
第4种情况k依次取最后一位的所有可能值，我们通过减少到相同的规模较小的问题，将数字的数量与最后一位k的乘积p相加。
如果您使用记忆实现 dp，这将有O( n * p )运行时间。
PS：我的回答是针对比 OP 描述的更普遍的问题。如果必须满足没有数字必须等于 1 的条件，则可以将公式调整如下：
f[ n ][ p ] = 8 * ( 9^(n-1) - 8^(n-1) ), if p = 0
0, if n = 1 and p >= 10 or p = 1
1, if n = 1 and 1 < p < 10
sum{ f[ n - 1 ][ p / k ] for 1 < k < 10, p mod k = 0 }, if n > 1
于 2013-01-07T10:24:15.327 回答
1
对于N个数字，其数字的乘积是p；
例如，如果 n = 3 且 p =24
安排如下（排列）
= (p!)/(p-n)!
= (24!) /(24 -3)!
= (24 * 23 * 22 * 21 )! / 21 !
= (24 * 23 * 22 )
= 12144
所以可以进行12144安排
对于组合如下
= (p!)/(n!) * (p-n)!
= (24!) /(3!) * (24 -3)!
= (24 * 23 * 22 * 21 )! / (3!) * 21 !
= (24 * 23 * 22 ) / 6
= 2024
愿这对你有帮助
于 2013-01-07T10:05:01.523 回答
1
这些问题似乎是人为的，但无论如何你所看到的都有上限。例如 p 不能有大于 7 的素数除数，因为它必须是单个数字（“使得其数字的乘积”）。
因此假设 p = 1 * 2^a * 3^b * 5^c * 7^d。
2^a 可以来自 ceil(a/3) 到 'a' 数字。3^b 可以来自 ceil(b/2) 到 'b' 位。5^c 和 7^d 可以分别来自 'c' 和 'd' 数字。其余数字可以用 1 填充。
因此 n 的范围可以从 ceil(a/3)+ceil(b/2)+c+d 到无穷大，而 p 具有一组固定值。
于 2013-01-07T10:25:46.320 回答
1
素数分解感觉是正确的方向，尽管您不需要任何大于 7 的素数，因此您可以重复除以 2、3、5、7。（如果我们没有得到一个素数，或者得到一个> 7，则没有解决方案）。
一旦我们有了主要因素，p % x并且p / x可以实现为恒定时间操作（您实际上不需要p，您可以只保留主要因素）。
我的想法是，用下面的算法计算组合，从那里得到的排列很容易。
getCombinations(map<int, int> primeCounts, int numSoFar, string str)
if (numSoFar == n)
if (primeCounts == allZeroes)
addCombination(str);
else
;// do nothing, too many digits
else if (primeCounts[7] >= 1) // p % 7
getCombinations(primeCounts - [7]->1, numSoFar-1, str + "7")
else if (primeCounts[5] >= 1) // p % 5
getCombinations(primeCounts - [5]->1, numSoFar-1, str + "5")
else if (primeCounts[3] >= 2) // p % 9
getCombinations(primeCounts - [3]->2, numSoFar-1, str + "9")
getCombinations(primeCounts - [3]->2, numSoFar-2, str + "33")
else if (primeCounts[2] >= 3) // p % 8
getCombinations(primeCounts - [2]->3, numSoFar-1, str + "8")
getCombinations(primeCounts - [2]->3, numSoFar-2, str + "24")
getCombinations(primeCounts - [2]->3, numSoFar-3, str + "222")
else if (primeCounts[3] >= 1 && primeCounts[2] >= 1) // p % 6
getCombinations(primeCounts - {[2]->1,[3]->1}, numSoFar-1, str + "6")
getCombinations(primeCounts - {[2]->1,[3]->1}, numSoFar-2, str + "23")
else if (primeCounts[2] >= 2) // p % 4
getCombinations(primeCounts - [2]->2, numSoFar-1, str + "4")
getCombinations(primeCounts - [2]->2, numSoFar-2, str + "22")
else if (primeCounts[3] >= 1) // p % 3
getCombinations(primeCounts - [3]->1, numSoFar-1, str + "3")
else if (primeCounts[2] >= 1) // p % 2
getCombinations(primeCounts - [2]->1, numSoFar-1, str + "2")
else ;// do nothing, too few digits
考虑到事情的完成顺序，我认为不会有重复。
改进：
p%7一旦你看过，你就不需要再看一遍（在堆栈的更深处） p%5，因为我们知道它不能再被 7 整除，所以很多这些检查都可以优化掉。
primeCounts不必是map，可以是长度为4的数组，也不必复制，可以适当增减数值即可。也可以做类似的事情str（字符数组）。
如果 的数字太多，则检查或getCombinations(..., str + "8")没有意义。这个和类似的检查不应该太难实现（只要让函数返回一个布尔值）。"24""222"
于 2013-01-07T11:04:00.970 回答