A1103. Integer Factorization

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₁^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² + 4² + 2² + 2² + 1², or 11² + 6²+ 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₁, a₂, ... a_K } is said to be larger than { b₁, b₂, ... 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

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<vector>
 5 using namespace std;
 6 vector<int> ans, temp, fac;
 7 int N, K, P, maxSumfac = -1;
 8 void dfs(int index, int cnt, int sum, int sumfac){
 9     if(sum == N && cnt == K){
10         if(sumfac > maxSumfac){
11             maxSumfac = sumfac;
12             ans = temp;
13         }
14         return;
15     }
16     if(index <= 0 || sum > N || cnt > K)
17         return;
18     if(fac[index] + sum  <= N){
19         temp.push_back(index);
20         dfs(index, cnt + 1, sum + fac[index], sumfac + index);
21         temp.pop_back();
22     }
23     dfs(index - 1, cnt, sum, sumfac);
24 }
25 int power(int n, int p){
26     int bas = 1;
27     for(int i = 0; i < p; i++)
28         bas *= n;
29     return bas;
30 }
31 int main(){
32     scanf("%d %d %d", &N, &K, &P);
33     int i, num;
34     for(i = 0; ; i++){
35         num = power(i, P);
36         if(num > N)
37             break;
38         fac.push_back(num);
39     }
40     if(num > N)
41         dfs(i - 1, 0, 0, 0);
42     else dfs(i, 0, 0, 0);
43     if(ans.size() == 0){
44         printf("Impossible");
45     }else{
46         printf("%d = %d^%d", N, ans[0], P);
47         int len = ans.size();
48         for(int i = 1; i < len; i++){
49             printf(" + %d^%d", ans[i], P);
50         }
51     }
52     cin >> N;
53     return 0;
54 }

View Code

总结：

1、本题题意：给出N、P、K，要求选出K个数，使得他们分别的P次方再求和等于N。按照降序输出序列，且若有多个答案，选择一次方和最大的一个输出。

2、预处理，计算中肯定需要反复用到一个数的P次方，如果每次用时都计算，显然太慢且重复。可以提前预计算一个数组，i的P次方为 fac[i] 。具体范围应该计算到 i 的P次方大于N的那个i。然后dfs从i - 1开始递减搜索。在main函数开始的地方不要忘记写预处理的语句。同样，当前序列的和应该在选择过程中计算，而不是每次都重复计算。

3、注意不要少写递归结束的语句。当结果符合要求时需要return，但不符合要求时也需要return。

4、vector<int> ans, temp；ans、temp一个存全局最优答案，一个存当前答案，两者可以直接赋值，其内容是拷贝。

5、注意index <= 0时也不符合条件，需要加到搜索结束的条件中去。