PAT(A) 1103. Integer Factorization (30)

原题目：

原题链接：https://www.patest.cn/contests/pat-a-practise/1103

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

题目大意

输入N，K，P； 将N由K个数表示出来，这K个数必须是某个正整数的P次方。输出结果中K个数降序排列，如果存在多个，取使得K个正整数之和最大的那一组。

解题报告

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;

本题警示

本人在此题上写了一个代码，第5个点总是过不去，经过两个晚上的debug，发现全局变量被修改了，原本init()函数里并没有“sumOfAns = 0;”这句代码，在执行第5个测试点时，init()执行完之后，sumOfAns的值就被修改为441，十分莫名其妙，故加上了一句。并写了一个博文以记录。 C++全局变量值被修改

代码

 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"<<endl;
        return;
    }
    cout<<N<<" = "<<ans[1]<<"^"<<P;
    for(int i= 2; i <= K; i++){
        cout<<" + "<<ans[i]<<"^"<<P;
    }
    cout<<endl;
}

int main(){
    init();
    dfs(N,maxNum,K);
    printAns();
    system("pause");
}