C++で m + sum(m) + sum(sum(m)) = N を満たす数の個数を求める方法

入力として整数 N が与えられます。この記事の目的は、次の条件を満たす N 以下の数 m の個数を求めることです。ここで N ≤ 10⁹ とします。

m + sum(m) + sum(sum(m)) = N　ここで、sum(m) は m の各桁の合計（桁和）を表します。

例えば、m が 137 の場合、sum(m) = 1 + 3 + 7 = 11 となり、sum(sum(m)) = sum(11) = 1 + 1 = 2 となります。

例で理解しよう

例 1

入力: N = 27

出力: m + sum(m) + sum(sum(m)) = N を満たす数の個数: 3

説明: 該当する数は以下の 3 つです。

9（9 + 9 + 9 = 27）

15（15 + (1 + 5) + (6) = 27）

21（21 + (2 + 1) + (3) = 27）

例 2

入力: N = 81

出力: m + sum(m) + sum(sum(m)) = N を満たす数の個数: 2

説明: 該当する数は以下の 2 つです。

63（63 + (6 + 3) + 9 = 81）

66（66 + (6 + 6) + (1 + 2) = 81）

プログラムで使用するアプローチ

このアプローチでは、各数の桁和を計算し、その合計が N と一致するかどうかを確認します。計算した合計が N と等しければカウントを 1 つ増やし、最後にそのカウントを結果として返します。

取り得る最大の数は 10⁹ であるため、m の桁和の最大値は 81（9 × 9）、さらに sum(sum(m)) の桁和の最大値は 16（79 の場合は 7 + 9 = 16）となります。つまり、m 自身の値を除いた合計の増分は最大でも 97 です。したがって、N − 97 から N までの範囲の数だけを調べれば十分です。N − 97 より小さい数や N より大きい数は、この条件を満たすことがないからです。

• 整数 N を入力として受け取ります。
• 関数 total(int num) は、引数として受け取った数の桁和を返します。
• 桁和を格納する res_total と、現在の桁を表す res を、ともに 0 で初期化します。
• while ループを使って、各桁を順番に処理します。
• res = num % 10 で一の位を取り出し、res_total に加算します。
• num を 10 で割り、次の桁へ進みます。
• 最後に res_total を、num の桁和として返します。
• 関数 condition(int N) は N を受け取り、m + sum(m) + sum(sum(m)) を満たす数の個数を返します。
• カウントを 0 で初期化します。
• for ループで i = N − 97 から i ≤ N まで走査します。
• 桁和を temp_1 = total(i) として計算します。
• total(i) の桁和を total(temp_1) として計算します。
• temp_3 = i + temp_1 + temp_2 を求め、N と等しければカウントを増やします。
• for ループの終了後、カウントを結果として返します。

コード例

#include <bits/stdc++.h>
using namespace std;
int total(int num) {
    int res_total = 0;
    int res = 0;
    while (num > 0) {
        res = num % 10;
        res_total = res_total + res;
        num = num / 10;
    }
    return res_total;
}
int condition(int N) {
    int count = 0;
    for (int i = N - 97; i <= N; i++) {
        int temp_1 = total(i);
        int temp_2 = total(temp_1);
        int temp_3 = i + temp_1 + temp_2;
        if (temp_3 == N) {
            count++;
        }
    }
    return count;
}
int main() {
    int N = 9999;
    cout << "m + sum(m) + sum(sum(m)) = N を満たす数の個数: " << condition(N);
    return 0;
}

上記のコードを実行すると、次のような出力が得られます。

出力

m + sum(m) + sum(sum(m)) = N を満たす数の個数: 2