088. 积和数(Product-sum numbers)

若自然数\(N\)能够同时表示成一组至少两个自然数\(\{a_1,a_2,\cdots,a_k\}\)的积与和,也就是说:

$$ N=a_1+a_2+\cdots+a_k=a_1\times a_2\times \cdots a_k $$
\(N\)被称为积和数。例如\(6\)是一个积和数,因为\(6 = 1 + 2 + 3 = 1 \times 2 \times 3\)。给定集合的元素个数\(k\),我们称满足上述性质的最小\(N\)值为最小积和数。当\(k = 2,3,4,5,6\)时,最小积和数如下所示:
$$ \begin{align*} &k=2: 4 = 2 × 2 = 2 + 2\\ &k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3\\ &k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4\\ &k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2\\ &k=6: 12 = 1 × 1 × 1 × 1 × 2 × 6 = 1 + 1 + 1 + 1 + 2 + 6 \end{align*} $$
因此,对于\(2≤k≤6\),所有的最小积和数的和为\(4+6+8+12 = 30\),注意\(8\)只被计算了一次。已知对于\(2≤k≤12\),所有最小积和数构成的集合是\(\{4, 6, 8, 12, 15, 16\}\),这些数的和是\(61\)

对于\(2≤k≤12000\),所有最小积和数的和是多少?

分析:这道题是前一百题中解决的人数最少的题,也有很多人认为是前一百题中最难的一道题。我觉得这道题的难度并不在于解决思路,而是如何用代码的形式实现这种解决思路。我也是参考了多处资料,经过多次尝试,最终使用递归的方式来解决这个问题。最终的代码比较简短,执行效率也很好,但是理解起来还是有一些难度。

初步分析一下题目,要求特定\(k\)对应的最小积和数,设其为\(mps(k)\)。对于合数\(n\),我们可以把它分解成其因子的乘积,我们现在只考虑大于一的因子,也就是说我们忽略一和其自身这一对因子。假设\(n\)可以分析为\(r\)个大于一的因子的乘积,即\(n=\prod_{i=1}^rd_i\)。同时,我们也可以求出这些因子的和\(s=\sum_{i=1}^rd_i\)。对于大于二的因子,其乘积总是大于其和,其差为\(f=n-s\)。为了使得积与和相等,则我们可以在和的这一边补充\(f\)\(1\),使和增加至\(n\);而补充1并不会改变乘积。因此,此时总的因子个数\(k=r+f=r+n-s\)。比如对于\(12\),可将其分解\(12=2\times6\),而2和6的和为8,因此我们需要在和这一边补充四个一,因此总的因子数为\(2+4=6\)

上面讨论了如何计算\(k\),下面我们看一下对于特定的\(k\),其对应的积和数\(n\)的取值范围。假设数\(n\)可以表示成\(k\)个因子的积与和,则这些因子中至少有一个必须大于二,否则这个数就变成一了,因此这\(k\)个因子的和至少要大于\(k\),即有\(n>k\)。通过稍微复杂些的推理,我们还可以推出\(n\le2k\)。因此对于特定的\(k\),其对应的自然数取值范围为\((k,2k]\)。因此题目要求2至12000范围内的最小积和数,我们只需要搜寻\((2,24000]\)范围内的自然数就可以了。我们可以从这个范围内的自然数中可以重复的取出两个、三个以及更多个元素,计算它们的乘积并保证乘积不超过24000,假设其乘积为\(p\),和为\(s\),个数为\(f\),则对应的\(k=p-s+f\)。我们对这个\(k\)对应的\(n\)存储在列表中,并对其不断更新,如果发现了一个更小的\(n\),则用新的\(n\)替换。这样在遍历结束后,我们的列表中保存的就是特定的\(k\)对应的\(mps(k)\)。用集合对这个列表去重并求和,即为题目所求。

# time cost = 163 ms ± 1.13 ms

def main():

    def update_min_n_arr(p,s,f,start):
        k = p - s + f
        if k < 12001:
            min_n_arr[k] = min(min_n_arr[k],p)
            for i in range(start,12000//p*2):
                update_min_n_arr(p*i,s+i,f+1,i)

    min_n_arr = [24000]*12001
    update_min_n_arr(1,1,1,2)
    return sum(set(min_n_arr[2:]))