PAT A1103 Integer Factorization (30point(s))

Scroll Down

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

If there is no solution, simple output Impossible.

Sample Input 1:

169 5 2

Sample Output 1:

169 = 62+62+62+62+52

Sample Input 2:

169 167 3

Sample Output 2:

Impossible

题意

给出三个数,K,N,P,找出K个不同的数,使它们的P次幂的和为N,如果有多种结果,选择“更大的集”,如果所有满足条件的集合都相等,则选择因子和最大的的集合。

解答

本题很显然是要使用dfs剪枝算法,需要注意时间复杂度。
对于数的P次幂,不应在寻找答案时计算,应该在最开始就计算,这样能节省大量时间。
dfs剪枝算法如下

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

int N, K, P, maxFacSum = -1;
vector<int> v, ans, tempAns;

// index为数组v的索引,应该从v.size()-1,即最后一个位置往前遍历,因为
// 要“更大的集合”,;tempSum为当前累加值,如果tempSum大于N,应该提前返
// 回;tempK为当前深度,如果temK等于K,说明不能再添加元素到集合里了,如
// 果此时tempSum不等于N,说明该集合不是答案,应该返回;facSum为所有因
// 子的和。
void dfs(int index, int tempSum, int tempK, int facSum) {
	if (tempK == K) {
		// 满足条件
		if (tempSum == N && facSum > maxFacSum) {
			ans = tempAns;
			maxFacSum = facSum;
		}
		return;
	}
	while (index >= 1) {
		if (tempSum + v[index] <= N) {
			tempAns[tempK] = index;
			// inedx既是索引也是因子
			dfs(index, tempSum + v[index], tempK + 1, facSum + index);
		}
		index--;
	}
}
int main() {
	cin >> N >> K >> P;
	int temp = 0;
	for (int i = 1; temp <= N; i++) {
		v.push_back(temp);
		temp = (int)pow(i, P);
	}
	tempAns.resize(K);
	dfs(v.size() - 1, 0, 0, 0);
	if (maxFacSum == -1) {
		printf("Impossible");
		return 0;
	}
	printf("%d = ", N);
	for (int i = 0; i < ans.size(); i++) {
		if (i != 0) printf(" + ");
		printf("%d^%d", ans[i], P);
	}
	return 0;
}