PAT 1103 Integer Factorization (30分)

原题链接：1103 Integer Factorization (30分)

关键词：DFS + 剪枝

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[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 12​2​​ +4​2​​ +2​2​​ +2​2​​ +1​2​​ , or 11​2​​ +6​2​+22​​ +22​​ +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 { a1,a2​​ ,⋯,ak​​ } is said to be larger than { b1​​ ,b2​​ ,⋯,bk​​ } 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:

Sample Output 1:

Sample Input 2:

Sample Output 2:

Impossible
           

题目大意： 给你一个整数N，让你分解成K个整数的P次方之和，如果仍不能确定唯一解法，则选择因子序列更大的解法。

分析：

1. 先把i从0开始所有的i的p次方的值存储在v[i]中，直到v[i] > n为止；
2. dfs，记录当前正在相加的index（即v[i]的i的值），当前的总和

   tempSum

   ，当前K的个数

   tempK

   ，因为题目中要求输出因子的和最大的那个，所以保存一个

   facSum

   为当前因子的和，让它和

   maxFacSum

   比较，如果比maxFacSum大就更新maxFacSum和要求的ans数组的值。

代码：

//pat 1103
#include <bits/stdc++.h>
using namespace std;

int N, k, p;
vector<int> v, ans, tempAns; 
int maxFacSum = -1;	//目前最大的因子之和	

void dfs(int index, int tempSum, int tempK, int facSum){
	if(tempK == k){	//k的数目对了 
		if(tempSum == N && facSum > maxFacSum){	//满足要求且因子之和更大，就更新 
			ans = tempAns; 			
			maxFacSum = facSum;
		}
		return;
	} 

    while(index >= 1) {
        if (tempSum + v[index] <= N) {
            tempAns[tempK] = index;
            dfs(index, tempSum + v[index], tempK + 1, facSum + index);
        }
        if (index == 1) return;
        index--;	//从大王小枚举
    }
}

int main(){
	cin >> N >> k >> p;
	
	//初始化v
	int temp = 0, index = 1;
	while(temp <= N){
		v.push_back(temp);
		temp = pow(index, p);
		index++;
	}
	
	tempAns.resize(k);
	dfs(v.size() - 1, 0, 0, 0);
	
	if(maxFacSum == -1) puts("Impossible");
	else{
		printf("%d = ", N);
		for(int i = 0; i < ans.size(); i ++ ){
			if(i) printf(" + ");
			printf("%d^%d", ans[i], p);
		}
	}
	
	
	return 0;
}