【C++】桁和がNに等しくMで割り切れる、0を含まない数を範囲内でカウントする方法

問題の概要

2つの整数 START と END が与えられ、この間に数値の範囲が定義されます。この記事の目的は、範囲 [START, END] 内にある数のうち、次の3つの条件をすべて満たすものを見つけることです。

• どの桁にも「0」が含まれていないこと
• 各桁の合計(桁和)が指定された数 N と一致すること
• 指定された数 M で割り切れること

解き方はシンプルです。START から END まで順に数を走査し、while ループを使って各数の桁和を計算します(すべての桁が 0 以外である場合のみ)。その桁和が N と一致し、かつ M で割り切れる場合にカウントを1増やします。

それでは、具体例で確認してみましょう。

入力例 1

START=1 END=100 N=9 M=6

出力例 1

Numbers with digit sum N and divisible by M: 4

説明: 18、36、54、72 の4つの数は、いずれも桁和が 9 であり、6 で割り切れます。また、どの数にも 0 は含まれていません。

入力例 2

START=100 END=200 N=10 M=2

出力例 2

Numbers with digit sum N and divisible by M: 4

説明: 118、136、154、172 の4つの数は、いずれも桁和が 10 であり、2 で割り切れます。こちらも 0 を含む桁はありません。

アルゴリズムの考え方

以下のプログラムで採用しているアプローチの手順は次のとおりです。

• 整数 START、END、N、M を受け取ります。
• 関数 digitSum(int start, int end, int n, int m) は、「桁和が n に等しく、m で割り切れ、かつ 0 を含まない桁のみを持つ数」の個数を返します。
• 該当する数を数えるための変数 count を 0 で初期化します。
• 桁和を格納する変数 digsum を用意します。
• 判定用のフラグとして変数 flag を 0 で初期化します。
• for ループで i = start から i = end まで範囲内の数を走査します。
• 各数 num = i について、num % m == 0(m で割り切れる)場合のみ処理を進めます。
• while ループで num > 0 の間、各桁を取り出して調べます。
• digit = num % 10 として桁を取得し、digit が 0 以外なら digsum += digit で加算し、num = num / 10 として次の桁へ進めます。途中で 0 の桁が見つかった場合は flag = 0 として while ループを抜けます。
• while ループ終了後、digsum == n かつ flag == 1 であれば count をインクリメントします。
• その後、i を m の倍数ずつ増やすことで走査を効率化します(for ループ自体が i++ するため、i-- で調整しています)。
• すべてのループが終わった時点で、count には条件を満たす数の総数が格納されています。
• count を結果として返します。

C++実装例

#include <bits/stdc++.h>
using namespace std;
int digitSum(int start, int end, int n, int m){
    int count = 0;
    int digsum = 0;
    int flag=0;
    for (int i = start; i <= end; i++){
        int num=i;
        digsum=0;
        flag=0;
        if(num%m==0){
            while(num>0){
                int digit=num%10;
                if(digit==0){
                    flag=0;
                    break;
                }
                digsum+=num%10; // 桁の合計を計算
                num=num/10;
                flag=1;
            }
            if(digsum==n && flag==1) // 判定対象は元の数 i {
                count++;
                cout<<i<<" ";
            }
            i+=m; // 以降は m の倍数ずつ進める
            i--; // for ループの i++ との調整
        }
    }
    return count;
}
int main(){
    int START = 1;
    int END = 100;
    int N = 9;
    int M = 6;
    cout <<"Numbers with digit sum N and divisible by M: "<<digitSum(START,END,N, M);
    return 0;
}

出力

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

Numbers with digit sum N and divisible by M: 4

補足:計算量について

この手法では、m の倍数だけを走査対象とするため、実際に調べる数は約 (END − START) / M 個に絞られます。各数の桁和計算は桁数 d に対して O(d) で行えるため、全体の計算量はほぼ O(((END − START) / M) × log₁₀END) となります。範囲が極端に広いケースでは桁DP(デジタルDP)などの高度な手法が有効ですが、本記事のような範囲であれば、この単純な全走査方式でも十分実用的です。