A fatoração K−P de um inteiro positivo N consiset em experssar N como a soma das P-ésimas potências de K inteiros positivos. O objetivo é desenvolver um programa que determine tal fatoração para quaisquer N, K e P positivos.

Especificação de Entrada:

Cada caso de teste é fornecido em uma única linha contendo três inteiros positivos: N (≤400), K (≤N) e P (1<P≤7). Os valores são separados por espaço.

Especificação de Saída:

Quando existir uma solução, a saída deve seguir o formato:

N = n[1]^P + ... + n[K]^P

onde n[i] (para i = 1, ..., K) representa o i-ésimo fator. Os fatores devem ser listados em ordem não crescente.

Observação: a solução pode não ser única. Por exemplo, a fatoração 5-2 de 169 possui nove soluções, como 12^2+4^2+2^2+2^2+1^2 ou 11^2+6^2+2^2+2^2+2^2, entre outras. A saída deve corresponder à solução com a maior soma dos fatores. Em caso de empate, escolhe-se a sequência lexicograficamente maior — uma sequência { a1, a2, ..., aK } é considerada maior que { b1, b2, ..., bK } se existir um L (1≤L≤K) tal que ai = bi para i<L e aL > bL.

Se não houver solução, a saída deve ser simplesmente "Impossible".

Exemplo de Entrada 1:

169 5 2

Exemplo de Saída 1:

169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2

Exemplo de Entrada 2:

169 167 3

Exemplo de Saída 2:

Impossible

A seguir, apresenta-se uma implementação em C++ que utiliza recursão para explorar todas as combinações possíveis. O código foi reestruturado com nomes de variáveis e lógica modificados, mantendo a correção do algoritmo original.

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

void buscarFatoracao(int limite, int k_atual, int soma_pot, int soma_bases, 
                     int n, int k, int p, const vector<int>& potencias,
                     vector<int>& seq_corrente, vector<int>& seq_melhor, 
                     int& soma_maxima) {
    if (soma_pot == n && k_atual == k) {
        if (soma_bases > soma_maxima) {
            soma_maxima = soma_bases;
            seq_melhor = seq_corrente;
        }
        return;
    }
    
    if (soma_pot > n || k_atual > k || limite < 1) {
        return;
    }
    
    seq_corrente.push_back(limite);
    buscarFatoracao(limite, k_atual + 1, soma_pot + potencias[limite], 
                    soma_bases + limite, n, k, p, potencias, 
                    seq_corrente, seq_melhor, soma_maxima);
    seq_corrente.pop_back();
    
    buscarFatoracao(limite - 1, k_atual, soma_pot, soma_bases, n, k, p, 
                    potencias, seq_corrente, seq_melhor, soma_maxima);
}

int main() {
    int n, k, p;
    cin >> n >> k >> p;
    
    vector<int> potencias;
    int max_base = 0;
    while (pow(max_base, p) <= n) {
        potencias.push_back(pow(max_base, p));
        max_base++;
    }
    
    vector<int> seq_corrente;
    vector<int> seq_melhor;
    int soma_maxima = -1;
    
    buscarFatoracao(max_base - 1, 0, 0, 0, n, k, p, potencias, 
                    seq_corrente, seq_melhor, soma_maxima);
    
    if (soma_maxima == -1) {
        cout << "Impossible" << endl;
    } else {
        cout << n << " = ";
        for (size_t i = 0; i < seq_melhor.size(); ++i) {
            if (i > 0) cout << " + ";
            cout << seq_melhor[i] << "^" << p;
        }
        cout << endl;
    }
    
    return 0;
}