C++ প্রোগ্রাম: সংখ্যাকে n-th পাওয়ারের যোগফল হিসেবে এক্সপ্রেস করার উপায়

সংখ্যা X-কে ইউনিক প্রাকৃতিক সংখ্যাদের n-th পাওয়ারের যোগফল হিসেবে কতভাবেই এক্সপ্রেস করা যায়, সেটি বের করতে হবে।

উদাহরণ

X=100, n=2 → 3 ways:
100 = 10²
100 = 6² + 8²
100 = 1² + 3² + 4² + 5² + 7²

অ্যালগরিদম (রিকার্শন + ব্যাকট্র্যাকিং)

1. 1 থেকে floor(X^(1/n)) পর্যন্ত ট্রাই করুন।
2. প্রতিটি i এর জন্য i^n বিয়োগ করে রিকার্শন কল করুন।
3. remaining == 0 হলে কাউন্ট বাড়ান।

C++ কোড উদাহরণ

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

int countWays(int X, int n, int start=1) {
    if (X == 0) return 1;
    int maxBase = (int)pow(X, 1.0/n);
    int ways = 0;
    for (int i = start; i <= maxBase; i++) {
        int p = (int)pow(i, n);
        if (p <= X) ways += countWays(X-p, n, i+1);
    }
    return ways;
}

int main() {
    cout << countWays(100, 2) << endl; // 3
    return 0;
}

আউটপুট

3