1103. Integer Factorization (30)

àì夳堔傛蜴生んèń 2022-05-28 07:29 128阅读 0赞

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:**

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

--------------------

题目大意：

代码：

#include<stdio.h>
    #include<vector>
    #include<math.h>
    using namespace std;
    int n,k,p;
    vector<int> v;
    int Maxsum=-1;
    vector<int> ansv,tmpv;
    void init()
    {
        int tmp=0,i=1;
        while(tmp<=n)
        {
            v.push_back(tmp);
            tmp=pow(i,p);
            i++;
        }
    }
    void DFS(int index,int tmpn,int tmpk,int tmpsum)
    {
        if(tmpn==n&&tmpk==k)
        {
            if(Maxsum<tmpsum)
            {
              ansv=tmpv;
              Maxsum=tmpsum;
            }
            return ;
        }
        if(tmpn>n||tmpk>k)
            return ;
        if(index>=1)
        {
           tmpv.push_back(index);
           DFS(index,tmpn+v[index],tmpk+1,tmpsum+index);
           tmpv.pop_back();
           DFS(index-1,tmpn,tmpk,tmpsum);
        }
    }
    int main()
    {
        int i,j,m,t;
        scanf("%d %d %d",&n,&k,&p);
        init();
        DFS(v.size()-1,0,0,0);
        if(Maxsum==-1)
        {
            printf("Impossible");
            return 0;
        }
        printf("%d",n);
        for(i=0;i< ansv.size();i++)
        {
            if(i==0)
            printf(" = %d^%d",ansv[i],p);
            else
            printf(" + %d^%d",ansv[i],p);
        }
        return 0;
    }