PAT 1103. Integer Factorization (30)

Posted on Edited on In

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 i<L and aL>bL 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

深搜加剪枝，首先减掉一些不能整开p次方的数，然后去搜索，然后再搜索的过程中，减掉不符合条件的

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
#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

vector<int> fac, final_path, path;
int maxFacSum = -1;

void init(int n, int p) {
    int i = 1, temp = 0;
    while (temp <= n) {
        fac.push_back(temp);
        temp = pow(i, p);
        i++;
    }
}

void dfs(int cur, int k, int n, int facSum) {
    if (k == 0 && n == 0) {
        if (maxFacSum < facSum) {
            maxFacSum = facSum;
            final_path = path;
        }
        return;
    }
    if (k < 0 || n < 0) return;

    if (cur >= 1) {
        path.push_back(cur);
        dfs(cur, k - 1, n - fac[cur], facSum + cur);
        path.pop_back();
        dfs(cur - 1, k, n, facSum);
    }
}

int main() {
    int k = 0, n = 0, p = 0;
    scanf("%d %d %d", &n, &k, &p);
    init(n, p);
    dfs(fac.size() - 1, k, n, 0);
    if (maxFacSum == -1) printf("Impossible");
    else {
        printf("%d = %d^%d", n, final_path[0], p);
        for (int i = 1; i < final_path.size(); i++) {
            printf(" + %d^%d", final_path[i], p);
        }
    }
    return 0;
}