# PAT(A) 1103. Integer Factorization (30)

### 1103. Integer Factorization (30)

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

### 解题报告

DFS搜索结果，为节省时间，先将正整数的P次方存入数组factor中，上限为i^P<=N。主要代码dfs(n,maxnum,k)的作用是将n用k个不超过正整数为maxnum的P次方的数表示出来。 当n==k==0时，即达到要求了，判断答案是否更好，若好，则替换。 其中有两个剪枝操作 1. 若全部由K个最大正整数的P次方表示也不能达到n，那肯定没有解决方案，剪枝剪掉。

 1 2 if(n > factor[maxnum] * k) return; 
1. 若n减去当前选择的正整数的P次方小于0，则肯定不会有结果，直接跳过。
 1 2  if(n - factor[i] < 0) continue; 

### 代码

  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 `#include "iostream" #include "math.h" using namespace std; int N,K,P; int factor[20 + 1]; int maxNum; int ans[400 + 5]; int sumOfAns = 0; int tempAns[400 + 5]; void init(){ cin>>N>>K>>P; maxNum = 1; factor[1] = 1; while(factor[maxNum] <= N){ maxNum ++; factor[maxNum] = pow(maxNum * 1.0,P); } maxNum --; sumOfAns = 0; } void dfs(int n,int maxnum,int k){ static int sum = 0; if(n > factor[maxnum] * k) return; if( ( n && (!k)) || ((!n) && k)) return; int i; if(n == 0 && k == 0){ if(sum > sumOfAns){ for(int j = 1; j <= K; j++) ans[j] = tempAns[j]; sumOfAns = sum; } return; } for(i = maxnum; i >= 1; i--){ if(n - factor[i] < 0) continue; tempAns[K - k + 1] = i; sum += i; dfs(n - factor[i],i,k-1); sum -=i; } } void printAns(){ if(!sumOfAns){ cout<<"Impossible"<