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 (≤), K (≤) and P (1). 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 1, or 1, 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 { , } is said to be larger than { , } if there exists 1 such that ai=bi for i<L and aL>bL.
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
我真的无语了,卡在测试点2卡了好久,怎么也没发现哪里不对,从刚写完代码的沾沾自喜到怎么调试也不过测试点2后上网搜索原因怀疑人生。结果发现是自己的==写成了!=,导致排序算法出错,沃柑!
错误真的是在你怎么也想不到的地方。
#include<iostream> #include<cmath> #include<vector> #include<algorithm> using namespace std; vector<vector<int>>solutions;//存放所有的可能solution int get_total(vector<int>a){ int rt=0; for(int i=0;i<a.size();i++)rt+=a[i]; return rt; } bool cmp(vector<int>a,vector<int>b){ int ta=get_total(a); int tb=get_total(b); if(ta!=tb){ return ta>tb; }else{ int i=0; while(a[i]==b[i])i++;//把等号写成不等号在这里测试点2卡了很久 return a[i]>b[i]; } } vector<int>te;//临时解决方法; int N,k,p; int get_int(int a,int p){ int te=1; for(int i=0;i<p;i++)te*=a; return te; } void DFS(int s,int tetotal,int p,int sk,int ed){ if(sk==k&&tetotal==s){ solutions.push_back(te); return; } if(tetotal==s&&sk<k)//数目不够 { return; } for(int i=ed;i>=1;i--){ if(tetotal+get_int(i,p)<=s&&sk+1<=k){ te.push_back(i); DFS(s,tetotal+get_int(i,p),p,sk+1,i);//这里是一个剪枝,保证得到的序列从大到小_(:з」∠)_ te.pop_back(); } } } int main(){ cin>>N>>k>>p; DFS(N,0,p,0,sqrt(N)+1);//因子的最大值不能比sqrt(N)+1还要大,所以遍历从sqrt(N)+1遍历就行了 if(solutions.size()==0){ cout<<"Impossible"; } else{ sort(solutions.begin(),solutions.end(),cmp); cout<<N<<" ="; for(int i=0;i<k;i++){ if(i!=0)cout<<" +"; cout<<" "<<solutions[0][i]<<"^"<<p; } } return 0; }