Integer Factorization

#include<bits/stdc++.h>
using namespace std;

int n,k,p,maxfacsum=-1;
vector<int> ans,temp,fac;

void Init() {
	int t=0,i=0;
	while(t<=n) {
		fac.emplace_back(t);
		t=pow(++i,p);
	}
}

void DFS(int index,int nowk,int sum,int facsum) {
	if(sum==n&&nowk==k) {
		if(maxfacsum<facsum) {
			maxfacsum=facsum;
			ans=temp;
		}
		return ;
	}
	if(sum>n||nowk>k) return ;
	if(index>=1) {
		temp.emplace_back(index);
		DFS(index,nowk+1,sum+fac[index],facsum+index);
		temp.pop_back();
		DFS(index-1,nowk,sum,facsum);
	}
}

int main() {
	scanf("%d %d %d",&n,&k,&p);
	Init();
	DFS(fac.size()-1,0,0,0);
	if(maxfacsum==-1) printf("Impossible");
	else {
		printf("%d = %d^%d",n,ans[0],p);
		for(int i=1; i<ans.size(); i++) {
			printf(" + %d^%d",ans[i],p);
		}
	}
	return 0;
}