C++で2からN/2までのすべての基数で表した数Nの桁の合計を求める方法

問題の概要

この問題では、ある数値Nが与えられます。私たちのタスクは、2からN/2までのすべての基数で数値Nを表したときの、各桁の数字の合計を求めるプログラムを作成することです。

つまり、数値を2からN/2までのすべての基数に変換する必要があります。例えば、n = 9の場合、基数は2、3、4となり、それぞれの基数における桁の合計をすべて足し合わせます。

入出力例

具体例を使って問題を理解しましょう。

入力:

N = 5

出力:

2

説明:

2からN/2までの基数は2のみです。
5を2進数で表すと「101」となり、桁の合計は 1+0+1 = 2 となります。

解決アプローチ

この問題を解くには、2からN/2までの各数値を基数として扱います。桁の合計を計算するには、Nを基数で繰り返し割り算し(N = N / base)、その余りを合計に加えていきます。最後に、各基数で求めた合計値をすべて足し合わせることで、最終的な答えが得られます。

実装例

以下は、この解法の動作を示すC++プログラムです。

#include <iostream>
using namespace std;
int findBaseSum(int n, int base, int &sum){
    while (n > 0) {
        sum += n % base;
        n /= base;
    }
    return sum;
}
void CalcSumOfBaseDigits(int n, int &sum){
    for (int base = 2; base <= n / 2; base++)
        findBaseSum(n, base, sum);
}
int main(){
    int N = 11;
    int sum = 0;
    CalcSumOfBaseDigits(N, sum);
    cout<<"The sum of digits of "<<N<<" written in all bases from 2 to "<<(N/2)<<" is "<<sum;
    return 0;
}

出力

The sum of digits of 11 written in all bases from 2 to 5 is 14

コードの解説

findBaseSum関数は、指定された基数で数値nを表したときの桁の合計を計算します。nが0になるまで、nを基数で割った余りを合計に加え、nを基数で割り続けます。

CalcSumOfBaseDigits関数は、基数2からN/2までループ処理を行い、各基数についてfindBaseSumを呼び出して合計を累積していきます。

このアルゴリズムの計算量は、基数ごとの桁数に依存するため、O(N log N)程度となります。数値Nが大きい場合でも効率的に動作する実用的な手法です。