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:]))