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 12​2​​+4​2​​+2​2​​+2​2​​+1​2​​, or 11​2​​+6​2​​+2​2​​+2​2​​+2​2​​, 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 { a​1​​,a​2​​,⋯,a​K​​ } is said to be larger than { b​1​​,b​2​​,⋯,b​K​​ } if there exists 1≤L≤K such that a​i​​=b​i​​ for i<L and a​L​​>b​L​​.

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

Realization idea:
This question is a very good one. i also use two ways to write dfs for this question, and the time efficiency of the two methods is almost more than 200ms (in the best case). Here are several details. Give priority to storing the power value of each number i into an array. If pow function is called to calculate the power value every time during recursion, the overall time of the algorithm will be doubled. The second point is to use pruning method during recursion, The redundant layer of recursion can be omitted. Although the answer is not unique, the larger the sum of the base of the sequence, the better. If it is equal, find the larger one of the single elements of the sequence. We only need to start from sqrt(N) to find the base. The reason why the base starts from sqrt(N) is because P is greater than 1 and the minimum is 2.

AC code

Method 1:
	#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int N,K,P,maxVal=-1;
vector<int> sq,ans,powKey;

void dfs(int idx,int sum,int p,int cnt) {//Sum of times: sum of times: cnt: sum of times
	if(sum==N) {
		if(sq.size()==K&&cnt>maxVal) {//When it is satisfied that the sum of K bases is N and the base sum is greater than the previous sequence 
			maxVal=cnt;
			ans=sq;
		}
		return;
	}
	if(idx>=1) {//Lower bound of base
		sq.push_back(idx);
		if(sum+powKey[idx]<=N&&sq.size()<=K) {//Pruning when the square of sum + current number is less than K and the current number is not more than k, it will enter the next layer of recursion
			dfs(idx,sum+powKey[idx],p,cnt+idx);//Select current number
		}
		sq.pop_back();
		dfs(idx-1,sum,p,cnt);//Do not select the current number
	}
}

int main() {
	cin>>N>>K>>P;
	powKey.resize(N+1);//Store the P-th power value of each number from 1 to n 
	for(int i=0; i<=N; i++)//Calculating the square of each number in advance can reduce the time cost by half
		powKey[i]=pow(i,P);
	dfs(sqrt(N),0,P,0);
	if(maxVal==-1) printf("Impossible");
	else {
		cout<<N<<" = ";
		for(int i=0; i<K; i++) {
			printf("%d^%d",ans[i],P);
			if(i<K-1) printf(" + ");
		}
	}
	return 0;
}

Method 2:
	#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int N,K,P,maxVal=-1;
vector<int> sq,ans,powKey;

void dfs(int idx,int sum,int p,int cnt) {//idx: base sum: sum of all times and p: power cnt: sum of bases
	if(sum==N) {
		if(sq.size()==K&&cnt>maxVal) {//When it is satisfied that the sum of K bases is N and the base sum is greater than the previous sequence 
			maxVal=cnt;
			ans=sq;
		}
		return;
	}
	if(idx>=1) {//Lower bound of base
		sq.push_back(idx);
		if(sum+powKey[idx]<=N&&sq.size()<=K) {//Pruning when the square of sum + current number is less than K and the current number is not more than k, it will enter the next layer of recursion
			dfs(idx,sum+powKey[idx],p,cnt+idx);//Select current number
		}
		sq.pop_back();
		dfs(idx-1,sum,p,cnt);//Do not select the current number
	}
}

int main() {
	cin>>N>>K>>P;
	powKey.resize(N+1);//Store the P-th power value of each number from 1 to n 
	for(int i=0; i<=N; i++)//Calculating the square of each number in advance can reduce the time cost by half
		powKey[i]=pow(i,P);
	dfs(sqrt(N),0,P,0);
	if(maxVal==-1) printf("Impossible");
	else {
		cout<<N<<" = ";
		for(int i=0; i<K; i++) {
			printf("%d^%d",ans[i],P);
			if(i<K-1) printf(" + ");
		}
	}
	return 0;
}

Expansion of this topic:
The idea of this question should also be used to:
1. Fix the load-bearing V in a backpack. Different items have different weights and prices. Under the condition of ensuring that the weight of items does not exceed V, the total value of items is the largest. This question is the only answer.

void DFS(int index, int sumW, int sumC) {
    if (index == n) {
        return;//The selection of n items has been completed
    }
	
    DFS(index + 1, sumW, sumC);//Don't choose the first item
    if (sumW + w[index] <= V) {//Pruning can only continue if the volume V is not exceeded after adding the first item
        if (sumC + c[index] > ans) {
            ans = sumC + c[index];//Update max value
        }
        DFS(index + 1, sumW + w[index], sumC + c[index]);//Choose the first item
    }
}

2. Given N integers (there may be negative numbers), select k numbers from them so that the sum of these K numbers is exactly equal to a given integer X; If there are multiple schemes, select the one with the largest sum of squares of the elements. Data guarantee that such a scheme is unique. For example, select two numbers from four integers {2,3,3,4} so that their sum is 6. Obviously, there are two schemes {2,4} and {3,3}, of which the scheme with the largest sum of squares is {2,4}. This is the case where the answer is not unique.

void DFS(int index, int nowK, int sum, int sumSqu) {
    if (nowK == k && sum == x) {//Find the sum of k numbers as X
        if (sumSqu > maxSumSqu) {//If it's better than what's currently found
            maxSumSqu = sumSqu;//Update maximum sum of squares
            ans = temp;//Update the optimal scheme
        }
        return;
    }
    //After n numbers have been processed, or more than k, or more than x, return
    if (index == n || nowK > k || sum > x)    return;

    //Number of selected numbers
    temp.push_back(A[index]);
    DFS(index + 1, nowK + 1, sum + A[index], sumSqu + A[index] * A[index]);
    temp.pop_back();
    //No index number selected
    DFS(index + 1, nowK, sum, sumSqu);
}

This type of questions can be summarized into a kind of dfs + pruning questions