如何计算除数一定的最小数？

如何计算除数一定的最小数？

您应该使用该公式计算整数的除数

n

：

d（n）=（a 1 +1）（a 2 +1） … （a k +1）

哪里

n = p 1 a 1 * p 2 a 2 * p 3 a 3 * … * p k a k

通过其主要除数的幂来唯一表示每个整数。这是一个著名的公式，但如果人们想知道如何得到它，需要注意的是

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除数的最小数。当您d出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     11      3,4,5,7    2     22      4,5,7,9    4     63      5,7,9,16   8     244      7,9,16,25  16    120

HTH。