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 = n1^P + … nK^P
where ni (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 122 + 42 + 22 + 22 + 12, or 112 + 62 + 22 + 22 + 22, 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:
|
1 |
169 5 2 |
Sample Output 1:
|
1 |
169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2 |
Sample Input 2:
|
1 |
169 167 3 |
Sample Output 2:
|
1 |
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 58 59 60 61 62 63 64 65 |
#include<stdio.h> #include<stdlib.h> #include<math.h> #include<memory.h> int npow(int base,int power) { int i,result=1; for(i=0;i<power;i++) { result*=base; } return result; } int max,result[400],buf[400]; int factor(int n,int begin,int k,int p,int sum) { int i,number,flag=0; if(k==0&&n==0) { if(sum>=max) { max=sum; memcpy(result,buf,400*sizeof(int)); } return 1; } if(k==0) { return 0; } for(i=begin;i<=sqrt(n);i++) { number=n-npow(i,p); if(number<k-1) { break; } sum+=i; buf[k-1]=i; if(factor(number,i,k-1,p,sum)) { flag=1; } sum-=i; } return flag; } int main() { int n,k,p,i; max=-1; scanf("%d%d%d",&n,&k,&p); factor(n,1,k,p,0); if(max==-1) { printf("Impossible\n"); return 0; } printf("%d = %d^%d",n,result[0],p); for(i=1;i<k;i++) { printf(" + %d^%d",result[i],p); } return 0; } |