gen_2019.cc

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

template<typename T> using V = vector<T>;
using pii = pair<int,int>;

const int N = 2019;

V<V<int>> potencies; // [base][exp]
V<pii> expressio; // {base,exp}

void f(int n, int base)
{   // Formes de escriure n com a suma de potencies de diferent base totes majors o iguals a <base>
    if (n == 0) {
        cout << N << " = ";
        for (int i = 0; i < expressio.size(); ++i) {
            if (i > 0) cout << " + ";
            cout << expressio[i].first << "^" << expressio[i].second+2;
        }
        cout << endl;
    }
    else if (n > 0 and base >= 1) {
        f(n, base-1);
        for (int exp = potencies[base].size()-1; exp >= 0; --exp) {
            expressio.push_back({base, exp});
            f(n-potencies[base][exp], base-1);
            expressio.pop_back();
        }
    }
}

int main()
{
    potencies.assign(N+1, V<int>());
    potencies[1].push_back(1);
    for (int base = 2; base <= N; ++base) {
        for (int v = base*base; v <= N; v *= base) { // mínim -> base^2
            potencies[base].push_back(v);
        }
    }
    f(N, 2019);
}