1 条题解

  • 1
    @ 2023-6-10 23:22:34

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

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

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

    但是我们猜想这样的情况很少,我打了个 11041 \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
    

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

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

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

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

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

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

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

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

    • 前文中提到的 p11p \leq 11

    显然,因为 13!=6227020800>10913! = 6227020800 > 10^9

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

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

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

    于是我们需要讨论 2,3,5,7,112, 3, 5, 7, 11 这五个质数,于是我们进行一个五维背包即可。时间复杂度为 O(τ(n)f(n))O(\tau(n) f(n)),其中 f(n)f(n) 表示最大的整数 xx 满足 x!nx! \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;
    }
    
    • 1

    信息

    ID
    282
    时间
    100ms
    内存
    512MiB
    难度
    4
    标签
    (无)
    递交数
    50
    已通过
    22
    上传者