## 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次方的数表示出来。

1. 若全部由K个最大正整数的P次方表示也不能达到n，那肯定没有解决方案，剪枝剪掉。
if(n > factor[maxnum] * k)
return;
1. 若n减去当前选择的正整数的P次方小于0，则肯定不会有结果，直接跳过。
if(n - factor[i] < 0)
continue;

C++全局变量值被修改

### 代码

#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");
}

还没有人评论...