The most intuitive solution you will ever find in this entire discussion. Plus, the run time speed surpassed editorial solution.

include

using namespace std;

int ipow(const int& b, const int& e){ if(e == 0) return 1; return b * pow(b, e - 1); }

int recursion_ans(const vector& vec, const int& index, const int& remaining){ if(remaining == 0) return 1; if(index < 0 || remaining < 0) return 0;

return recursion_ans(vec, index - 1, remaining - vec[index]) + 
        recursion_ans(vec, index - 1, remaining);

}

int main(){ int X, N; cin >> X >> N;

vector<int> vec;

int i = 1;
while(i){
    int value = ipow(i, N); ++i;
    if(value > X) break;
    vec.push_back(value);
}

cout << recursion_ans(vec, vec.size() - 1, X);

return 0;

}