A1103 Integer Factorization

Posted on | In |

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[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 12
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
If there is no solution, simple output Impossible.

1
2
3
4
5
6
7
8
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h> 
#define MAX 110
using namespace std;
typedef long long ll;
int n,k,p;
int pow(int x,int p){
	int sum=1;
	for(int i=1;i<=p;i++)
	sum*=x;
	return sum;
}
int maxi=-1;
vector<int> ans,tmp,fac;
void init(){
	fac.push_back(0); 
	for(int i=1;;i++){
		int t=pow(i,p);
			if(t>n) break;
		else fac.push_back(t);
	
	}
}
void dfs(int ind,int nk,int sum,int fsum){
	if(sum==n&&nk==k)
	{
		if(fsum>maxi){
			maxi=fsum;
			ans=tmp;
		}
		return;
	}
	if(sum>n||nk>k) return;
	if(ind>=1){
		tmp.push_back(ind);
		//选的话可以重复选 
		dfs(ind,nk+1,sum+fac[ind],fsum+ind);
		tmp.pop_back();
		//不选的分支 
		dfs(ind-1,nk,sum,fsum);
	}
}
int main(){
	cin>>n>>k>>p;
	init();

	dfs(fac.size()-1,0,0,0);
		if(ans.size()==0){
		cout<<"Impossible"<<endl;
		return 0;
	}
	cout<<n<<" = "; 
	for(int i=0;i<ans.size();i++){
		cout<<ans[i]<<"^"<<p;
		if(i!=ans.size()-1) cout<<" + ";
	}
	
}