# 题目

The KP 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 KP 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:

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,\cdots ,a_K \}$ is said to be larger than $\{b_1,b_2,\cdots ,b_K \}$ if there exists 1≤LK such that $a_i = b_i$ for i<L and $a_L > b_L$.

If there is no solution, simple output Impossible.

# 题解

## 思路

• 这道题题目意思有点抽象，但是借助例子应该能看懂。
• n 就是等号左边的数，K 就是右边加的那些项的个数，P就是指数
• 我们最大的底数是pow(n,1/P)，从1到这个数之间的所有数都是潜在的底数，且可以重复选取。
• 一开始我想到用DFS，以数值的大小为转移
• 但是这样的话，每次要对所有潜在的底数DFS，复杂度过高
• 更好的方法是以底数为转移，每次dfs更新底数

## 数据结构

• n,k,p 对应题目里的原数，项数和指数
• ans是最佳的底数们，是一个列表
• maxFacsum 是目前最佳的底数们的底数和
• sums 是目前计算中的指数和
• facsums 是目前计算中的底数和
• now 是目前计算中的底数们

## 算法

• 从最大的潜在底数开始DFS
• 更新sums和facsums和now
• 继续DFS这个底数——因为底数可以重复选取
• 回溯sums和facsums和now
• DFS上一个底数
• 当DFS到sums > n 或 now里面多于k了或者index 为0 的时候
• 及时剪枝
• 当DFS到sums = n 且 now的个数等于k的时候
• 比较最佳解和目前解的底数和，判断是否要更新最佳解。
• 输出即可

## 代码

• 这道题使用Python会有一个点超时。所以放上了Python和C++的两种解法。