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

本記事では、ある整数 X を「重複しない自然数の n 乗の総和」として表現する方法が何通りあるかを求めるプログラムについて解説します。

問題の概要

例として、X = 100、n = 2 の場合を考えてみましょう。このとき、100 を自然数の2乗（平方数）の和として表す方法は3通り存在します。

100 = 102
100 = 62 + 82
100 = 12 + 32 + 42 + 52 + 72

アルゴリズムの考え方

この問題は再帰を使うことで簡単に解くことができます。

基本的な手順は以下の通りです。

1 から対象となる数の n 乗根まで順に走査していきます。各ステップでは、自然数（1から開始）の n 乗の値を元の数から引き算し、残りの値が0未満になるまで処理を繰り返します。これにより、その整数を n 乗の和として表現できるすべての組み合わせを数え上げることができます。

同じ自然数を複数回使えないようにするため、再帰の呼び出しごとに「次に使える数の下限」を1つずつ大きくしていく点がポイントです。

C++での実装例

#include<iostream>
#include <math.h>
using namespace std;
int result = 0;
int ways(int number, int a, int init, int n){
    if (a == 0) {
        result++;
    }
    // 探索範囲の上限を設定
    int max = (int)floor(pow(number, 1.0 / n));
    for (int i = init + 1; i <= max; i++) {
        // n乗の値を順に引いていく
        int b = a - (int)pow(i, n);
        if (b >= 0)
            ways(number, a - (int)pow(i, n), i, n);
    }
    return result;
}
int main() {
    int a = 100, n = 2;
    cout << ways(a, a, 0, n);
    return 0;
}

実行結果

3

コードの解説

関数 ways は4つの引数を取ります。number は元の整数、a は現在残っている値、init は直前に使用した自然数、n は乗数です。a がちょうど0になった時点で1つの組み合わせが見つかったことになるため、カウンタ result をインクリメントします。

探索の上限は floor(number の n 乗根) として求められるため、それ以上の大きな数を調べる無駄を省いています。このような深さ優先探索による全列挙により、X = 100、n = 2 の場合は正しく「3」が出力されます。