C++で与えられた方程式の解の個数を求める方法

この問題では、3つの整数 A、B、C が与えられます。私たちの課題は、与えられた方程式を満たす解の個数を求めることです。

対象となる方程式

X = B*Sm(X)^A + C

ここで、Sm(X) は X の各桁の数字を合計した値（桁和）を表します。

つまり、1 以上 10⁹ 以下の範囲に存在する整数の中から、上記の方程式を満たすすべての X の値を数える必要があります。

具体例を見て、問題を理解しましょう。

入力:

A = 3, B = 6, C = 4

出力:

3

解法のアプローチ

この問題を効率よく解く鍵となるのが「桁和」です。X の最大値は 999999999（9が9個）なので、桁和の最大値は 81（9 × 9桁）となります。さらに重要な点として、桁和の値が決まれば、方程式の右辺 B*Sm(X)^A + C の値も一意に決まるという性質があります。

そこで、桁和の候補値を 1 から 81 まで順番に試します。各桁和の値から計算される解の候補について、実際にその数字の桁和が元の値と一致するか、そして値が 10⁹ 未満に収まっているかを確認すればよいのです。この方法なら、探索範囲はたった 81 通りしかなく、非常に高速に答えを求められます。

アルゴリズムの手順

1. 桁和の候補 digSum を 1 から 81 まで繰り返し処理する。
2. 各 digSum に対して、solVal = B × digSum^A + C を計算する。
3. solVal の各桁の合計を求め、digSum と一致し、かつ solVal が 10⁹ 未満であれば解としてカウントする。
4. 最終的なカウントを出力する。

C++による実装例

上記の解法の動作を示すプログラムは以下の通りです。

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

int countSolutions(int a, int b, int c){
    int solutionCount = 0;
    // 桁和の最大値は81（999999999の場合）
    for (int digSum = 1; digSum <= 81; digSum++) {
        int solVal = b * pow(digSum, a) + c;
        int temp = solVal;
        int sum = 0;
        // solValの桁和を計算
        while (temp) {
            sum += temp % 10;
            temp /= 10;
        }
        // 桁和が一致し、範囲内であれば解としてカウント
        if (sum == digSum && solVal < 1e9)
            solutionCount++;
    }
    return solutionCount;
}

int main(){
    int a = 3, b = 6, c = 4;
    cout<<"The number of solutions of the equations is "<<countSolutions(a, b, c);
    return 0;
}

出力

The number of solutions of the equations is 3

計算量について

この解法では、桁和の候補は最大 81 通り、さらに各候補に対する桁和の計算は最大でも 10 回程度の除算・剰余演算で済むため、全体の計算量はほぼ定数時間 O(1) と見なせます。X の範囲である 10⁹ 通りを全探索する必要がないため、非常に効率的なアプローチだと言えます。