长度为n的集合,满足所有元素的和等于所有元素的积,求对于长度为2-12000的集合,最小的这样的积和数组成的集合的和(即相同积和数只算一次)
这是一道40%的题,卡了Flu一个寒假.
观察样例,发现有个通解是 ${1,1,1,1,…,2,k}$ ,所以答案上界呼之欲出,就是24000.
但是发现有例外:
于是考虑对每个数暴力分解,然后求出这个数可能匹配上哪个长度,单个的复杂度是 $O(\sqrt n)$ 的.
但是所有数字一起分解就会省不少事,我们使用dfs,记录当前深度,乘积,加和,然后在dfs中进行分解.同时为了避免出现 $6=3\times2=2\times3$ 的情况,额外记录一个num表示上一个因数,保证因数单调,也就是每个分解最多出现1次,然后更新答案即可,复杂度如下,Flu不知道是多少,反正实际上跑的飞快(可能是数据太小了).
d(i)是i的因数个数