PAT-A1103

#include<stdio.h> #include<vector> using namespace std; int n, k, p, max_facsum=-1; vector<int> fac, temp, ans; int get_p(int a){ int loop=0, ans=1; while(loop<p){ans=ans*a; loop++;} return ans; } void DFS(int index, int nowk,int sum, int facsum){ if(nowk>k || sum>n)return; if(nowk==k && sum==n && facsum>max_facsum){ max_facsum=facsum; ans=temp; } if(index>0){ temp.push_back(index); DFS(index,nowk+1,sum+fac[index],facsum+index); //选 temp.pop_back(); DFS(index-1,nowk,sum,facsum); //不选 } } int main(){ int i=0, tt=0; scanf("%d%d%d",&n,&k,&p); while(tt<=n){ tt=get_p(i++); fac.push_back(tt); } DFS(fac.size()-1,0,0,0); if(max_facsum==-1)printf("Impossible\n"); else { printf("%d = %d^%d",n,ans[0],p); for(i=1;i<ans.size();i++) printf(" + %d^%d",ans[i],p); } return 0; }