您应该使用该公式计算整数的除数n：
哪里
通过其主要除数的幂来唯一表示每个整数。这是一个著名的公式，但如果人们想知道如何得到它，需要注意的是d分裂n，当且仅当d是形式的P 1 X 1 * P 2 X 2 * P 3 X 3 * ...... * P ? X k，其中每个x i在0和a i之间，因此选择x i每个都有i + 1的可能性。现在，只需应用乘积规则，即可获得所需的公式。
对于固定的d(n)（如您的情况），n显然可以通过仔细选择现有素数的幂或添加新素数来获得的最小值。让我们来看这个简单的示例：16：
d（x）=（a 1 +1）（a 2 +1） … （a k +1）= 16 = 2 4。
这意味着您最多有四个不同的素数，因此：
x = 2 a 1 * 3 a 2 * 5 a 3 * 7 a 4
其中i > =0。现在的问题是-为了获得的最小值x，是增加2的幂（即，增加1）还是使用7（即取4 = 1而不是）更好？a 4 = 0）？好了，检查起来很简单，2 * 3 * 5 * 7> 2 3 * 3 * 5 = 120，这就是为什么在这种情况下120是答案的原因。
如何概括这种方法？您应该创建最小堆，在其中放置素数的幂，注意除数的数量达到指定值。在16的情况下，该最小堆将包含数字2，3，5，7，2 2，3 2，2 4等为什么？因为16 = 2 4，所以（a i +1）的每一个都必须除以16，即它必须是2的幂。每次添加新的幂时，它应增加左手边（即变量d(x)）用2的幂表示，因为您的最终目标是找到2 500500除数的最小数。当您弹出p x时，堆会使用第一个质k数（在问题语句中k = 500500）初始化，并在每个步骤中初始化从堆中返回p 2x，结果乘以p x。对于d(x)= 16 = 2 4的分步解决方案：
Step Heap d(x) x
==========================
0 2,3,5,7 1 1
1 3,4,5,7 2 2
2 4,5,7,9 4 6
3 5,7,9,16 8 24
4 7,9,16,25 16 120
HTH。
602392714
清零编程群