C++で整数を一意な自然数のn乗の和として表現する方法の数を求める

このチュートリアルでは、ある整数が一意な（重複のない）自然数のn乗の和として表現できる方法の数を求めるプログラムをC++で作成します。

2つの整数 number（対象の数）と power（べき指数）が与えられます。このとき、number を重複のない自然数の n 乗の和として表現する方法が何通りあるかを求めます。具体例を見てみましょう。

入力例と出力例

• 入力： number = 50, power = 2
• 出力： 3

50 を 2乗の和で表現すると、次の3通りの方法があります。

• 50 = 7² + 1² = 49 + 1
• 50 = 6² + 3² + 2² + 1² = 36 + 9 + 4 + 1
• 50 = 5² + 4² + 3² = 25 + 16 + 9

解き方のアプローチ：再帰

この問題は再帰を使うことでシンプルに解けます。各自然数 i について「i のべき乗を使う」か「使わない」かの2択を試し、すべての組み合わせを探索します。手順は以下の通りです。

1. number と power を初期化します。
2. 適切な名前の再帰関数を定義します。引数として number、power、i を受け取ります。
3. number が負になるか、pow(i, power) が number より大きい場合は、その経路では表現できないため 0 を返します。
4. number が 0 になった場合、または pow(i, power) がちょうど number と等しい場合は、有効な表現が見つかったので 1 を返します。
5. 合計の方法数を求めるために、2つの再帰呼び出しを行います。
   • 1つ目の再帰呼び出し：i のべき乗を使用する場合。number から pow(i, power) を引き、i をインクリメントして呼び出します。
   • 2つ目の再帰呼び出し：i のべき乗を使用しない場合。number はそのままに、i をインクリメントして呼び出します。

コード例

それでは、実際のコードを見てみましょう。

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

int findPossibleWaysCount(int number, int power, int i = 1) {
    if (number < 0 || number < pow(i, power)) {
        return 0;
    }
    if (number == 0 || number == pow(i, power)) {
        return 1;
    }
    return findPossibleWaysCount(number - pow(i, power), power, i + 1)
         + findPossibleWaysCount(number, power, i + 1);
}

int main() {
    // numberとpowerを初期化
    int number = 50, power = 2;
    cout << findPossibleWaysCount(number, power) << endl;
    return 0;
}

出力

上記のコードを実行すると、次の結果が出力されます。

3

処理の流れのポイント

この再帰関数のポイントは、各ステップで「現在の数 i のべき乗を採用するかどうか」という分岐を作る点です。これにより、同じ自然数を2回以上使うことを自然に防ぎながら、すべての組み合わせを網羅的に調べることができます。

また、pow(i, power) が number を超えた時点でその経路を打ち切ることで、無駄な探索を省き、効率よく答えを求められます。

まとめ

この記事では、C++の再帰を活用して、整数を一意な自然数の n 乗の和として表現する方法の数を求めるプログラムを紹介しました。「使う・使わない」の二択による再帰的な探索は、部分和問題など他の組み合わせ問題にも応用できるテクニックなので、ぜひ理解しておきましょう。