首先有一个简单的暴力：对 $1 \sim n$ 内的所有数进行阶乘分解，然后 dfs + 剪枝即可。具体地，每次拆出的数大于等于 $< n$ 且现在还可以拆分出的最大质数。注意特判 $n = 1$。

考虑一个比较乱搞的想法：贪心地，为了让项数最少，我们可以考虑拆出 $(n - 1)!$ 作为最大的一项。

但这样对不对呢？显然是错误的，比如 $9! = 7! \times 3! \times 3! \times 2!$，但无法拆分为 $8!$ 乘上某些东西；再比如 $16! = 14! \times 5! \times 2! = 15! \times 2! \times 2! \times 2!$，这种方案并非最优。

但是我们猜想这样的情况很少，我打了个 $1 \sim 10^4$ 的表，如下（normal 表示符合猜想，special 表示不符合猜想）：

normal 1
normal 4
normal 6
normal 8
special 9
special 10
normal 12
special 16
normal 24
normal 32
normal 36
normal 48
normal 64
normal 72
normal 96
normal 120
normal 128
normal 144
normal 192
normal 216
normal 240
normal 256
normal 288
normal 384
normal 432
normal 480
normal 512
normal 576
normal 720
normal 768
normal 864
normal 960
normal 1024
normal 1152
normal 1296
normal 1440
normal 1536
normal 1728
normal 1920
normal 2048
normal 2304
normal 2592
normal 2880
normal 3072
normal 3456
normal 3840
normal 4096
normal 4320
normal 4608
normal 5040
normal 5184
normal 5760
normal 6144
normal 6912
normal 7680
normal 7776
normal 8192
normal 8640
normal 9216

更大的范围暴力不太能跑动了，于是我们可以猜想当 $n \geq 17$，有解时最优拆分中一定有 $(n - 1)!$。

那在假定猜想成立的情况下，我们怎么判断有没有解以及找到一组最优解呢？

考虑对 $n$ 进行拆分，不难发现这里的 $n$ 必须满足存在一个 $p \mid n$，使得 $n$ 的去重质因数集合恰好为 $\{2, 3, \cdots, p\}$（当然这不是充要条件）。

接下来考虑在本题数据范围内对该猜想进行验证。

• 若有解，则 $n!$ 的阶乘拆分中一定包含 $[lst_n, n)$ 中的恰好一个数。

证明显然，这就是算法一中的剪枝。

• 若有解，则 $\exist i \in [lst_n, n)$，$n!$ 的阶乘拆分中包含 $i!$ 且 $\frac{n!}{i!}$ 可以拆分为若干从 $2$ 开始的连续质数的乘积且幂次不增。

证明显然，这就是算法二中用到的结论的扩展。

• 前文中提到的 $p \leq 11$。

显然，因为 $13! = 6227020800 > 10^9$。

• 对结论二中 $i$ 的范围进行进一步精确的限制，可知 $i \in [\max(lst_n, n - 2), n)$。

直接在数据范围内找出所有可能的情况判断即可。

由粗略的打表结果可知：除了 $9!$ 最优拆分为 $7! \times 3! \times 3! \times 2!$、$10!$ 最优拆分为 $7! \times 5! \times 3!$、$16!$ 最优拆分为 $14! \times 5! \times 2!$ 外（其他粗略打表得出的情况均经过暴力验证无解），数据范围内没有其他不能通过拆分出 $(n - 1)!$ 来构造或拆分出 $(n - 1)!$ 不优的情况。

于是我们需要讨论 $2, 3, 5, 7, 11$ 这五个质数，于是我们进行一个五维背包即可。时间复杂度为 $O(\tau(n) f(n))$，其中 $f(n)$ 表示最大的整数 $x$ 满足 $x! \leq n$。

代码：

#include <stdio.h>

const int N = 5, M = 12, K = 29 + 7, P = 18 + 7, Q = 12 + 7, R = 10 + 7, S = 8 + 7;
int prime[N + 7] = {0, 2, 3, 5, 7, 11}, power[N + 7], val[M + 7][N + 7], dp[M + 7][K][P][Q][R][S], cnt[M + 7];

inline int min(int a, int b){
	return a < b ? a : b;
}

int main(){
	int n;
	scanf("%d", &n);
	if (n == 1){
		printf("1\n");
		printf("0");
		return 0;
	}
	if (n == 9){
		printf("4\n");
		printf("2 3 3 7");
		return 0;
	}
	if (n == 10){
		printf("2\n");
		printf("6 7");
		return 0;
	}
	if (n == 16){
		printf("3\n");
		printf("2 5 14");
		return 0;
	}
	int t = n;
	for (int i = 1; i <= N; i++){
		while (t % prime[i] == 0){
			t /= prime[i];
			power[i]++;
		}
	}
	if (t > 1){
		printf("-1");
		return 0;
	}
	int up = min(M, n - 1);
	for (int i = 0; i <= power[1]; i++){
		for (int j = 0; j <= power[2]; j++){
			for (int k = 0; k <= power[3]; k++){
				for (int l = 0; l <= power[4]; l++){
					for (int x = 0; x <= power[5]; x++){
						dp[1][i][j][k][l][x] = 2e9;
					}
				}
			}
		}
	}
	dp[1][0][0][0][0][0] = 0;
	for (int i = 2; i <= up; i++){
		for (int j = 1, k = i; j <= N; j++){
			val[i][j] = val[i - 1][j];
			while (k % prime[j] == 0){
				k /= prime[j];
				val[i][j]++;
			}
		}
		for (int j = 0; j <= power[1]; j++){
			for (int k = 0; k <= power[2]; k++){
				for (int l = 0; l <= power[3]; l++){
					for (int x = 0; x <= power[4]; x++){
						for (int y = 0; y <= power[5]; y++){
							dp[i][j][k][l][x][y] = dp[i - 1][j][k][l][x][y];
							if (j >= val[i][1] && k >= val[i][2] && l >= val[i][3] && x >= val[i][4] && y >= val[i][5]) dp[i][j][k][l][x][y] = min(dp[i][j][k][l][x][y], dp[i][j - val[i][1]][k - val[i][2]][l - val[i][3]][x - val[i][4]][y - val[i][5]] + 1);
						}
					}
				}
			}
		}
	}
	if (dp[up][power[1]][power[2]][power[3]][power[4]][power[5]] == 2e9){
		printf("-1");
	} else {
		printf("%d\n", dp[up][power[1]][power[2]][power[3]][power[4]][power[5]] + 1);
		for (int i = up; i >= 2; i--){
			while (dp[i][power[1]][power[2]][power[3]][power[4]][power[5]] < dp[i - 1][power[1]][power[2]][power[3]][power[4]][power[5]]){
				cnt[i]++;
				for (int j = 1; j <= N; j++){
					power[j] -= val[i][j];
				}
			}
		}
		for (int i = 2; i <= up; i++){
			for (int j = 1; j <= cnt[i]; j++){
				printf("%d ", i);
			}
		}
		printf("%d", n - 1);
	}
	return 0;
}