题解：AT_iroha2019_day1_f Head of The Dragon

题目大意

得知 \(n\) 和 \(k\) ,求出 \(n\) 是否能分解出 \(k\) 个因数相乘，输出按字典序最小一种情况。

步骤

1. 将 \(n\) 分解质因数。
2. 判断质因数个数是大于 \(k\)，否则输出 \(-1\) 。
3. 按照分解出来的质因数从小到大输出。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, k, sum = 1;
int v[105];
signed main() {
	cin.tie(0), cout.tie(0);
	cin >> n >> k;
	int cnt = 0, w = n;//cnt 记录因数个数，n 要被分解，用另一个变量存储原来的值
	for (int i = 2; i <= sqrt(w); i++) { //从 2 到 sqrt(n)
		if (cnt == k - 1 && n != 1) {//特判最后一个因数
			v[++cnt] = n;
			break;
		}
		while (n % i == 0) {
			if (cnt == k - 1 && n != 1) {//特判最后一个因数
				v[++cnt] = n;
				break;
			}
			n /= i;
			v[++cnt] = i;//记录因数
		}
	}
	if (cnt < k)	cout << -1;//因数个数不足 k ,输出 -1
	else {//输出
		for (int i = 1; i <= k; i++)
			cout << v[i] << " ";
	}


}