pat 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 = n₁^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² + 4² + 2² + 2² + 1², or 11² + 6² + 2² + 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 { a₁, a₂, ... a_K } is said to belarger than { b₁, b₂, ... 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

深搜+回溯。

#include<iostream> using namespace std; #include<stdio.h> #include<vector> #include<map> #include<queue> #include<string.h> #define MS(a,b) memset(a,b,sizeof(a)) int n,k,p,num[30],S,maxn=-1; vector<int>v; vector<int>ans; /* start:刚开始的数。 cnt:个数 reminder：表示当前剩余的和。 num[i]:i^p的值。 */ void dfs(int start,int cnt,int reminder) { int i; if(cnt==0) { if(reminder==0) { if(S>maxn) { S=maxn; ans.clear(); for(i=0;i<v.size();i++) ans.push_back(v[i]); } else if(S==maxn) { for(i=0;i<v.size();i++) if(ans[i]<v[i]) break; if(i!=v.size()) { ans.clear(); for(i=0;i<v.size();i++) ans.push_back(v[i]); } } } return ; } for(i=start;i<21;i++) { int k=num[i]; if(k>reminder)break; v.push_back(i); S=S+i; dfs(i,cnt-1,reminder-k); S=S-i; v.pop_back();//回溯的时候要把这个点删掉。 } } int main() { int i,j; scanf("%d %d %d",&n,&k,&p); for(i=1;i<21;i++) { num[i]=1; for(j=0;j<p;j++) num[i]=num[i]*i; } S=0; dfs(1,k,n); if(ans.empty()) printf("Impossible\n"); else { printf("%d = ",n); for(i=ans.size()-1;i>0;i--) printf("%d^%d + ",ans[i],p); printf("%d^%d\n",ans[i],p); } return 0; }