C++でNをXのべき乗の和として表すときの最小項数を求める方法

問題文

正の整数 N と X が与えられます。この課題では、N を X のべき乗の和(X⁰ + X¹ + … + Xⁿ)として表現し、使用するべき乗の項数を最小にすることが求められます。

和が N と等しくなるために必要な、べき乗の最小個数を出力してください。

たとえば、N = 15、X = 3 の場合、「3」のべき乗を 3 つ使って次のように表せます。

15 = (3² + 3¹ + 3¹)

アルゴリズム

以下の考え方に基づいて最終結果を計算します。

1. x = 1 の場合、答えは n そのもの(n = 1 + 1 + … と n 回の加算で表現)
2. 任意の数 n は n = x * a + b(0 ≤ b ≤ x-1)と表せる。b は 0 以上 x-1 以下の範囲にあるため、b は x⁰ を b 回加算した和として表現できる

考え方のポイント

このアルゴリズムは、実質的に「数 n を x 進法で表したときの各桁の数字の合計」を求める処理と同じです。n を x で割った余り(b)は、x⁰ が b 個必要であることを意味し、商は次の桁に対応します。この剰余の加算と除算を n が 0 になるまで繰り返すことで、必要なべき乗の総数が効率的に求まります。

実装例

#include <iostream>
using namespace std;
int minNumOfPower(int n, int x){
    if (x == 1) {
        return n;
    }
    int result = 0;
    while (n > 0) {
        result = result + (n % x);
        n = n / x;
    }
    return result;
}
int main(){
    int n = 15;
    int x = 3;
    cout << "Minimum number of powers = " <<
    minNumOfPower(15, 3) << endl;
    return 0;
}

出力

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Minimum number of powers = 3

N = 15 を 3 進法で表すと「120」(1×9 + 2×3 + 0×1)となり、各桁の合計は 1 + 2 + 0 = 3。これは実際に 3² を 1 個、3¹ を 2 個、計 3 つのべき乗で 15 が表せることを示しています。