题意： 给定
n
n
n，将
n
n
n分解成
k
k
k个不同因数的乘积，问
k
k
k个数的最小和为多少
数据范围：
2
≤
n
≤
1
0
6
2\leq n \leq 10^6
2≤n≤106
题解：
倒序枚举将
x
x
x分解成
i
i
i和
x
i
\frac{x}{i}
ix，即每次分解的
x
x
x从
n
n
n以内的最大
i
i
i倍数开始，依次递减
i
i
i。
这样可以保证对于重复的数字分解不会被计入。
如
n
=
16
n=16
n=16
①
f
[
2
]
=
2
f[2] = 2
f[2]=2
②
f
[
6
]
=
5
,
f
[
3
]
=
3
f[6] = 5,f[3] = 3
f[6]=5,f[3]=3
③
f
[
12
]
=
7
,
f
[
8
]
=
6
,
f
[
4
]
=
4
f[12] = 7, f[8] = 6, f[4] = 4
f[12]=7,f[8]=6,f[4]=4
④
f
[
15
]
=
8
,
f
[
10
]
=
7
,
f
[
5
]
=
5
f[15]=8,f[10]=7,f[5]=5
f[15]=8,f[10]=7,f[5]=5
⑤
f
[
12
]
=
m
i
n
(
8
,
7
)
=
7
,
f
[
6
]
=
6
f[12]=min(8,7)=7,f[6]=6
f[12]=min(8,7)=7,f[6]=6
⑥
f
[
14
]
=
9
,
f
[
7
]
=
1
f[14]=9,f[7]=1
f[14]=9,f[7]=1
⑦
f
[
16
]
=
10
,
f
[
8
]
=
m
i
n
(
6
,
8
)
=
6
f[16]=10,f[8]=min(6,8)=6
f[16]=10,f[8]=min(6,8)=6
可以发现在③时分解
x
x
x为
4
4
4和
x
4
\frac{x}{4}
4x，但此时
f
[
4
]
=
∞
f[4]=\infty
f[4]=∞，不会更新
f
[
16
]
f[16]
f[16]
代码： 原地址
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1000010;
ll f[N];
int main() {
int n; scanf("%d", &n);
memset(f, 0x3f, sizeof f);
f[1] = 0;
for(int i = 2; i <= n; ++i) {
for(int j = n / i * i; j >= i; j -= i)
f[j] = min(f[j], f[j / i] + i);
}
if(f[n] == n) ++f[n];
printf("%lld", f[n]);
return 0;
}
