Head of The Dragon [いろはちゃんコンテスト Day1 F]

https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_f

前提知識

• 素因数分解

解説

https://atcoder.jp/contests/iroha2019-day1/submissions/5194885

数列を見てみると、因数分解をしている感じになっている。
さて、どこから始めようか。
　
まずは、構成できない場合を考えてみる。
構成できない場合が答えとして用意されているときは、ここから考えるのがよくヒントになる。
各要素は2以上の整数である必要があるので、構成できない場合は、
素因数分解したときに、素因数が足りない場合となる。
　
素因数がK個より多くあるときに、辞書順で最小にするためにはどうすればいいか。
基本は昇順ソートしたときに、昇順ソートで置いていけば良さそう。
K個より多いときは、最後の要素になるべく集める方が辞書順で最小となる。
貪欲にやっていけばよさそう。
これを実装する。
　
enumprで素因数分解している。

int N, K;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K;
	
	auto ep = enumpr(N);
 
	int sm = 0;
	fore(p, ep) sm += p.second;
	if (sm < K) {
		cout << "-1" << endl;
		return;
	}
 
	vector<int> ans;
	int other = 1;
	fore(p, ep) {
		rep(cn, 0, p.second) {
			if (ans.size() < K - 1) {
				ans.push_back(p.first);
			}
			else other *= p.first;
		}
	}
	ans.push_back(other);
 
	rep(i, 0, K) {
		if (i) printf(" ");
		printf("%d", ans[i]);
	}
	printf("\n");
}