如何计算除数一定的最小数？
从欧拉计划问题500
除数的数量为16。实际上，120是具有16个除数的最小数量。
用2 ** 500500除数找到最小的数。给您的答案取模500500507。
计算n的除数很简单，例如。在Python中len([i for i in range(1,n+1) if n % i == 0])。这是O（n）。
我尝试了蛮力搜索，发现带有32个除数的最小数字是840，但是对于上述问题来说太慢了。从不平等来看count_divisors(n) <=
n，这个数字将是巨大的。
你怎么看？有任何想法吗？如何计算除数一定的最小数？
：我不认为这是重复的。这个问题更具体，它涉及 数量
更大的特定类别。
回答：
您应该使用该公式计算整数的除数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。
以上是 如何计算除数一定的最小数？ 的全部内容， 来源链接： utcz.com/qa/421001.html
