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.
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.
For each case, if the solution exists, output in the format:
N = n[1]^P + ... n[K]^Pwhere 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=bi for i<L and aL>bL.
If there is no solution, simple output Impossible.
题目大意：将一个正整数N分解成K个正整数的P次方和，在多个结果里面找出因子之和最大的，若因子之和相同，字典序大的为答案。
思路：主要是DFS的思想，建立一个数组F，用来储存 1~m的P次方，m^P为≤N的最大正整数。find()里面传入四个变量，n为当前find()里面的for循环次数；cnt初始值为K，cnt=0作为递归的边界；tmpSum储存因子之和；sum是总和，sum=N才是符合条件的备选答案~
下一层的递归里的n总是小于等于上一层递归里的n，所以保证了字典序，不需要画蛇添足地写compera函数来筛选答案了（一开始就是因为这个操作导致测试点2答案错误），若无必要，勿增操作。
#include <iostream> #include <vector> #include <cmath> using namespace std; int N, K, P, m, fSum = -1; vector <int> ans, F, tmpA; void find(int n,int cnt, int tmpSum, int sum); int main() { scanf("%d%d%d", &N, &K, &P); int i = 1; F.push_back(0); while (1) { int x = pow(i, P); if (x > N) break; else { F.push_back(x); i++; } } m = F.size() - 1; find(m, K, 0, 0); if (ans.empty()) { printf("Impossible\n"); return 0; } printf("%d =", N); for (int i = 0; i < K; i++) { printf(" %d^%d", ans[i], P); if (i < K - 1) { printf(" +"); } } printf("\n"); return 0; } void find(int n, int cnt, int tmpSum, int sum) { if(n==0) return; if (cnt == 0) { if (fSum < tmpSum) { if (sum == N) { ans = tmpA; fSum = tmpSum; } } return; } for (int i = n; i > 0; i--) { if (sum <= N) { tmpA.push_back(i); find(i, cnt - 1, tmpSum + i, sum + F[i]); tmpA.pop_back(); } } }
