PAT A1103

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 = n1^P + … nK^P

where ni (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=bi for ibL

If there is no solution, simple output “Impossible”.

Sample Input 1:
169 5 2
Sample Output 1:
169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2
Sample Input 2:
169 167 3
Sample Output 2:
Impossible

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include "stdio.h"
//#include "math.h"
#include "string.h"
//#include "iostream"
//#include "stdlib.h"
#include "vector"
//#include "set"
//#include "map"
//#include "stack"
//#include "queue"
#include "algorithm"
using namespace std;

//typedef long long LL;
//n, k, p如题所述,maxFacSum记录最大底数之和
int n, k, p, maxFacsum = -1;
//fac记录了0^p, 1^p...i^p ,使i^p为不超过n的最大数
//ans存放最优底数列,temp存放递归中的临时底数数列
vector<int> fac, ans, temp;
//power 函数计算x^p
int power(int x){
int ans = 1;
for (int i = 0; i < p; i++) {
ans *= x;
}
return ans;
}
//init函数预处理fac数组,注意把0也存进去
void init(){
int i = 0, temp = 0;
while (temp <= n) {//当i^p没有超过n时,不断把i^p加入fac
fac.push_back(temp);
temp = power(++i);
}
}
//dfs函数,当前访问fac[index], nowK为当前选中个数
//sum为当前选中数之和,facSum为当前选中底数之和
void DFS(int index, int nowK, int sum, int facSum){
if (sum == n && nowK == k) {//找到一个满足的序列
if (facSum > maxFacsum) {//如果底数之和更大
ans = temp;
maxFacsum = facSum;
}
return;
}
if (sum > n || nowK > k) return;//这种情况不会产生答案,直接返回
if(index - 1 >= 0){//fac[0]不需要选择
temp.push_back(index);//把底数index加入临时序列temp
DFS(index, nowK + 1, sum + fac[index], facSum + index);//"选"的分支
temp.pop_back();//"选"的分支结束后把刚加进去的数pop掉
DFS(index - 1, nowK, sum, facSum);//"不选"的分支
}
}
int main(){
scanf("%d%d%d", &n, &k, &p);
init();//初始化fac数组
DFS(fac.size() - 1, 0, 0, 0);//从fac的最后一位开始往前搜索
if (maxFacsum == -1) {
printf("Impossible\n");
}else{
printf("%d = %d^%d", n, ans[0], p);//输出ans结果
for (int i = 1; i < ans.size(); i++) {
printf(" + %d^%d", ans[i], p);
}
}

return 0;
}