PAT-A-1103-Integer Factorization

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,⋯,a**K } is said to be larger than { b1,b2,⋯,b**K } 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:

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

Code

//大数处理会出现段错误，不完全正确，待更新
#include <iostream>
#include <vector>
using namespace std;

vector<int> res;
int index,_factsum=0;
bool flag = false;//表示还没有找到结果
//计算幂次数
int caculate(int num, int exp) {
	int fact = 1;
	for (int i = 0;i < exp;i++)
		fact *= num;
	return fact;
}

bool compareFactors(vector<int>& factors) {
	for (int i = 0;i < factors.size();i++) {
		if (factors[i] == res[i])
			continue;
		else if (factors[i] > res[i])
			return true;
	}
	return false;
}

void DFS(int start, int n, int sum, int exp, vector<int>& factors,int factsum) {
	if (sum == 0 && n>0)
		return;
	if (sum == 0 && n == 0) {
		if (flag) {
			if(factsum < _factsum)
				return;
			//比较数组的因子大小
			if (factsum==_factsum&&!compareFactors(factors))
				return;
		}
			
		flag = true;
		res = factors;
		_factsum = factsum;
		return;
	}

	for (int i = start;i > 0;i--) {
		//过滤不满足条件的选项
		int num = caculate(i, exp);
		if ((sum - num) < 0)
			continue;
		//做选择
		factors.push_back(i);
		DFS(i, n - 1, sum - num, exp, factors, factsum+i);
		//撤销选择
		factors.pop_back();
	}
}

int main() {

	int n, m, exp;
	scanf("%d%d%d", &n, &m, &exp);
	index = m;
	vector<int> factors;
	DFS(n,m, n, exp, factors,0);
	if (res.size() > 0) {
		printf("%d = ", n);
		for (int i = 0;i < (int)res.size();i++) {
			printf("%d^%d", res[i], exp);
			if (i != res.size() - 1)
				printf(" + ");
		}
	}
	else
		printf("Impossible\n");
	return 0;
}