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

Question

来自Project Euler问题500

120的除数是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,这个数字将是巨大的.

你怎么看？有任何想法吗？如何用一定数量的除数计算最小数？

---

编辑:我不认为这是重复的.这个问题是更具体的,它涉及一类特殊的多更大的数字.在其他问题通常要求.它的答案不适用于这个问题,它的大小不同.

Answer 1

你应该使用整数除数的公式n:

d(n)=(a ₁ +1)(a ₂ +1)...(a _k +1)

哪里

n = p ₁ ^{a ₁}*p ₂ ^{a ₂}*p ₃ ^{a ₃}*...*p _k ^{a _k}

是通过其主要除数的每个整数的唯一表示.这是一个著名的公式,但如果人们不知道如何得到它,注意d分n当且仅当d是形式的P ₁ ^{X ₁}*P ₂ ^{X ₂}*P ₃ ^{X ₃}*......*P _ķ ^{X _k},其中x _i中的每一个在0和a _i之间,因此存在用于选择x _i中的每一个的_i + 1种可能性.现在只需应用产品规则即可获得所需的公式.

对于固定d(n)(如在您的情况下),n显然通过仔细选择现有素数的幂或通过添加新素数来获得最小值.让我们通过这个简单的例子,16:

d(x)=(a ₁ +1)(a ₂ +1)...(a _k +1)= 16 = 2 ⁴.

这意味着您最多有4个不同的素数,因此:

x = 2 ^{a ₁}*3 ^{a ₂}*5 ^{a ₃}*7 ^{a ₄}

其中a _i > = 0.现在的问题是 - 为了获得最小值x,增加2的幂(即增加₁)或使用7(即取₄ = 1代替a ₄ = 0)？好吧,检查很简单,2*3*5*7> 2 ³*3*5 = 120,这就是120在这种情况下回答的原因.

如何推广这种方法？你应该创建min-heap,你将放置素数的幂,注意除数的数量达到指定值.在16的情况下,该最小堆将包含数字2,3,5,7,2 ²,3 ²,2 ⁴等为什么？因为16 = 2 ⁴,所以每个(a _i +1)必须除以16,即它必须是2的幂.每当你增加新的功率时,它应该增加左手边(即变量d(x))由2的幂,因为你的最终目标是找到2 ⁵⁰⁰⁵⁰⁰除数的最小数字.使用第一个k素数(在问题语句中k = 500500)初始化堆,并且在每个步骤中,当您从堆中弹出p ^x时,返回p ^2x并将结果乘以p ^x.d(x)= 16 = 2 ⁴的逐步解决方案:

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.