Source:

PAT A1103 Integer Factorization (30 分)

Description:

The K−P factorization of a positive integer N is to write N as the sum of the P-th power of Kpositive 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 (≤), K (≤) and P (1). 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 1, or 1, 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 { , } is said to be larger than { , } if there exists 1 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

Keys:

• 深度优先搜索（Depth First Search）

Attention:

• 不同的编译环境pow函数的精度不同，PAT跑的数据是对的，但我电脑上跑出来是错的，可以自己写一个

Code:

 1 /*
 2 time: 2019-07-02 18:55:08
 3 problem: PAT_A1103#Integer Factorization
 4 AC: 18:08
 5 
 6 题目大意：
 7 将整数N分解为以P为指数的K个因式的和
 8 输入：
 9 正整数N<=400，因式个数K，指数1<P<=7
10 输出：
11 按底数递减，
12 若不唯一，打印底数和最大的一组，
13 若不唯一，打印字典序较大的一组
14 
15 基本思路：
16 深度优先搜索，至第K层时若存在解，则选择最优解
17 */
18 #include<cstdio>
19 #include<vector>
20 #include<cmath>
21 using namespace std;
22 int k,n,p,optValue=0;
23 vector<int> fac,temp,ans;
24 
25 void DFS(int index, int numK, int sum, int sumFac)
26 {
27     if(numK==k && sum==n && sumFac>optValue)
28     {
29         optValue = sumFac;
30         ans = temp;
31     }
32     if(numK>=k || sum>=n || index<=0)
33         return;
34     temp.push_back(index);
35     DFS(index,numK+1,sum+fac[index],sumFac+index);
36     temp.pop_back();
37     DFS(index-1,numK,sum,sumFac);
38 }
39 
40 int main()
41 {
42 #ifdef ONLINE_JUDGE
43 #else
44     freopen("Test.txt", "r", stdin);
45 #endif // ONLINE_JUDGE
46 
47     scanf("%d%d%d", &n,&k,&p);
48     for(int i=0; pow(i,p)<=n; i++){
49         fac.push_back(pow(i,p));
50     }
51     DFS(fac.size()-1,0,0,0);
52     if(ans.size() == 0)
53         printf("Impossible");
54     else
55     {
56         printf("%d = %d^%d", n,ans[0],p);
57         for(int i=1; i<ans.size(); i++)
58             printf(" + %d^%d", ans[i],p);
59     }
60 
61     return 0;
62 }