The K−P factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the K−P factorization of N for any positive integers N, K and P.

Input Specification:

Each input file contains one test case which gives in a line the three positive integers N (≤400), K (≤N) and P (1<P≤7). The numbers in a line are separated by a space.

Output Specification:

For each case, if the solution exists, output in the format:
N = n[1]P + ... n[K]P
where n[i] (i = 1, ..., K) is the i-th factor. All the factors must be printed in non-increasing order.

Note: the solution may not be unique. For example, the 5-2 factorization of 169 has 9 solutions, such as 122+42+22+22+12, or 112+62+22+22+22, or more. You must output the one with the maximum sum of the factors. If there is a tie, the largest factor sequence must be chosen -- sequence { a1, a2,⋯,ak} is said to be larger than { b1, b2,⋯,bk} if there exists 1≤L≤K such that ai=bifor i<L and aL>bL.

If there is no solution, simple output Impossible.

169 5 2

Sample Output 1:

169 = 62+62+62+62+52

169 167 3

Impossible

解答

dfs剪枝算法如下

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

int N, K, P, maxFacSum = -1;
vector<int> v, ans, tempAns;

// index为数组v的索引，应该从v.size()-1，即最后一个位置往前遍历，因为
// 要“更大的集合”，；tempSum为当前累加值，如果tempSum大于N，应该提前返
// 回；tempK为当前深度，如果temK等于K，说明不能再添加元素到集合里了，如
// 果此时tempSum不等于N，说明该集合不是答案，应该返回；facSum为所有因
// 子的和。
void dfs(int index, int tempSum, int tempK, int facSum) {
if (tempK == K) {
// 满足条件
if (tempSum == N && facSum > maxFacSum) {
ans = tempAns;
maxFacSum = facSum;
}
return;
}
while (index >= 1) {
if (tempSum + v[index] <= N) {
tempAns[tempK] = index;
// inedx既是索引也是因子
dfs(index, tempSum + v[index], tempK + 1, facSum + index);
}
index--;
}
}
int main() {
cin >> N >> K >> P;
int temp = 0;
for (int i = 1; temp <= N; i++) {
v.push_back(temp);
temp = (int)pow(i, P);
}
tempAns.resize(K);
dfs(v.size() - 1, 0, 0, 0);
if (maxFacSum == -1) {
printf("Impossible");
return 0;
}
printf("%d = ", N);
for (int i = 0; i < ans.size(); i++) {
if (i != 0) printf(" + ");
printf("%d^%d", ans[i], P);
}
return 0;
}