A1103 Integer Factorization (30 point(s))

因子计算

1. 原文

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^2+4^2+2^2+2^2+1^2, or 11^2+6^2+2^2+2^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 { a1,a2,⋯,aK } is said to be larger than { b1,b2,⋯,bK } if there exists 1≤L≤K 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. 解析

预存结果

 int sum=0;
int idx=1;
while(sum<=n){
	v.push_back(sum);
	sum=pow(idx,p);
	idx++;
}

void dfs(int index,int sum,int cntK,int factsum)

递归求最大因子和的等式

3. AC代码

#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
vector<int> v,path,tempath;
int n,k;
int maxsum=-1;
void dfs(int index,int sum,int cntK,int factsum){
	if (cntK==k)
	{
		if (sum==n&&factsum>maxsum)
		{
			maxsum=factsum;
			path=tempath;
		}
		return;
	}
	while(index>=1){
		if (sum+v[index]<=n)
		{
			tempath[cntK]=index;
			dfs(index,sum+v[index],cntK+1,factsum+index);
		}
		if (index==1)
		{
			return;
		}
		index--;
	}

}
int main()
{
	int p;
	scanf("%d%d%d",&n,&k,&p);
	int sum=0;
	int idx=1;
	while(sum<=n){
		v.push_back(sum);
		sum=pow(idx,p);
		idx++;
	}
	tempath.resize(k);
	dfs(v.size()-1,0,0,0);
	if (maxsum==-1)
	{
		printf("Impossible\n");
	}else{
		printf("%d = %d^%d", n,path[0],p);
		for (int i = 1; i < path.size(); ++i)
		{
			printf(" + %d^%d",path[i],p);
		}
		printf("\n");
	}
	return 0;
}