P7947 [✗✓OI R1] 铝锤制作 题解

题目要求构造一个序列（元素均为正整数），使得各元素之积为 ，之和为 。

一种简单的构造方案如下：

考虑到 乘任何数都得任何数，因此序列中的 并不会对积做贡献，我们可以先把元素之积 凑出来，最后和不够可以补 。

但是单个数越大，可操作的空间就越小——
如 时，如果单纯地将 分成 和 ，和会超过 ，程序会认为在该条件下无法构造出一个合法的序列。

因此，我们如果要最大限度地构造出合法的序列，需要使每个数都尽量地小。由此引出对 进行质因数分解这样的做法。

具体的做法是：

1. 对 进行质因数分解，并将分解得到的质因数加入答案序列
2. 设质因数之和为 ：
   • 若 ，则将 个 加入答案序列，最终输出答案序列；
   • 若 ，则直接输出答案序列；
   • 若 ，则无解，输出 。

#include <cstdio>

int n, k, m, f = 2, s, a[1010];

inline void get_prime_factors() {
	while (f * f <= n) {
		while (n % f == 0) {
			a[++m] = f; // 将质因数加入答案序列
			s += f; // 统计质因数的和
			n /= f;
		}
		f++;
	}
	if (n != 1) {
		a[++m] = n;
		s += n;
	}
}

int main() {
	scanf("%d%d", &n, &k);
	get_prime_factors();
	
	if (s > k) {
		puts("-1");
		return 0;
	}
	
	for (int i = s; i < k; i++) {
		a[++m] = 1;
	}
	
	printf("%d\n", m);
	
	for (int i = 1; i <= m; i++) {
		printf("%d%c", a[i], " \n"[i == m]);
	}
	
	return 0;
}