1103 Integer Factorization (30分)
1103
分析：
将N表示成K个正整数的P次方之和，如果有多种方案，则输出底数之和最大的那种方案，且必须按照底数从大到小的顺序输出。
C++:
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
int n, k, p;
int maxFacSum = -1;
vector<int> fac, res, temp;
void init() {
int index = 1, temp = 0;
while (temp <= n) {
fac.push_back(temp);
temp = pow(index++, p);
}
}
void dfs(int index, int nowK, int sum, int facSum) {
if (sum == n && nowK == k) {
if (facSum > maxFacSum) {
res = temp;
maxFacSum = facSum;
}
return;
}
if (sum > n || nowK > k) {
return;
}
if (index - 1 >= 0) {
temp.push_back(index);
dfs(index, nowK + 1, sum + fac[index], facSum + index);
temp.pop_back();
dfs(index - 1, nowK, sum, facSum);
}
}
int main() {
scanf("%d%d%d", &n, &k, &p);
init();
dfs(fac.size() - 1, 0, 0, 0);
if (maxFacSum == -1) {
printf("Impossible\n");
} else {
printf("%d = %d^%d", n, res[0], p);
for (int i = 1; i < res.size(); i++) {
printf(" + %d^%d", res[i], p);
}
}
return 0;
}
