PAT-A1103.Integer Factorization

TheK−Pfactorization of a positive integerNis to writeNas the sum of theP-th power ofKpositive integers. You are supposed to write a program to find theK−Pfactorization ofNfor any positive integersN,KandP.
Input Specification:
Each input file contains one test case which gives in a line the three positive integersN(≤400),K(≤N) andP(1
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 as12​^2​​+4​^2​​+2^​2​​+2​^2​​+1​^2​​, or11​^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 {a​1​​,a​2​​,⋯,a​K​​} is said to belargerthan {b​1​​,b​2​​,⋯,b​K​​} if there exists1≤L≤Ksuch thata​i​​=b​i​​forib​L​​.
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

注意点

は、配列の下のスケールが数の二乗に対応するように、各数のp乗を事前に保存することができる.

dfsを利用して1つの選択数を利用する場合、後から前へ選択することができ、辞書順の最大値を保証し、辞書順を判断する必要がない.

はxのp次べき乗を熟練して計算する.

コード#コード#

#include  
#include 
#include 

using namespace std;

const int N = 410;

int n, k, p;
int maxSumF = -1; 
int a[N];

vector fac, temp, ans;

int power(int x)
{
    int ans = 1;
    for (int i = 0; i < p; i ++)
        ans *= x;
    return ans;
}

int init()
{
    int i = 0, temp = 0;
    while (temp <= n)
    {
        fac.push_back(temp);
        temp = power(++ i);
    }
}


void dfs(int index, int nowK, int sum, int sumF)
{
    if ( nowK == k )
    {
        if (sum == n && sumF > maxSumF)        
        {
            maxSumF = sumF;
            ans = temp;
        }
        return;
    }
    
    if (sum > n || nowK > k) return;
    
    //  
    if (index - 1 >= 0)
    {
        temp.push_back(index);
        dfs(index, nowK  + 1, sum + fac[index], sumF + index);
        temp.pop_back();
    
        //   
        dfs(index - 1, nowK, sum, sumF);    
    }

}



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

参考資料『アルゴリズムノート』.