【分析】

这题类似于01背包问题，我这里用DFS的递归方法遍历所有情况，并加上了剪枝。同时参考别人的方法，可以考虑用“打表”记录各个数的p次方的表，这样可以避免重复计算，降低复杂度，避免倒数第二个测试点超时。

【代码】

#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
int k, p, n;
int maxFac = -1;
vector<int> v, ansV;

/*
// 打表，一次性算出来，避免后面重复计算 
vector<int> fac, ans, temp;
 
int power(int x){
	int ans = 1;
	for(int i = 0; i < p; i++){
		ans *= x;
	}
	return ans;
} 
 
void init(){
	int i = 0, temp = 0;
	while(temp <= n){
		fac.push_back(temp);
		temp = power(++i);
	}
}
*/

void DFS(int index, int num, int sumFac, int sumP) {

	if(num > k || sumP > n) {
		return;
	}
	
	if(num == k && sumP == n) {
		if(sumFac > maxFac) {
			maxFac = sumFac;
			ansV = v;
		}

		return;
	}
	else if(num == k && sumP != n) {
		return;
	}

	if(num + 1 <= k && sumP + pow(index, p) <= n) {
		v.push_back(index);
		DFS(index, num+1, sumFac+index, sumP + pow(index, p));
		v.pop_back();
		
	}
	if(index > 1 ) {
		DFS(index - 1, num, sumFac, sumP);
	}
	
}

int main() {
	scanf("%d%d%d", &n, &k, &p);
	DFS((int)pow(1.0*n, 1.0/p), 0, 0, 0);
	if(maxFac == -1) {
		printf("Impossible\n");
	}
	else {
		printf("%d =", n);
		for(int i = 0; i < k; i++) {
			if(i != 0) {
				printf(" +");
			}
			printf(" %d^%d", ansV[i], p);
		}
	}

	return 0;
}