C++で範囲内の数値のうち「0以外のすべての桁」で割り切れる数をカウントする方法

この記事では、2つの整数 START と END が与えられ、これらによって数値の範囲が定義されます。ゴールは、範囲 [START, END] 内に含まれる数値のうち、「その数値自身の0以外のすべての桁」で割り切れるものをすべて見つけ出すことです。

実装では、STARTからENDまで順番に数値を走査し、各数値についてwhileループを用いて「0以外のすべての桁で割り切れるか」を判定します。条件を満たした場合はカウントを1つ増やします。

それでは、具体例を使って理解を深めましょう。

例1

入力：

START=10 END=20

出力：

0以外のすべての桁で割り切れる数値の個数: 5

説明：

10, 11, 12, 15, 20 の5つの数値は、それぞれが持つ0以外のすべての桁で割り切れます。

例2

入力：

START=100 END=200

出力：

0以外のすべての桁で割り切れる数値の個数: 25

説明：

0以外のすべての桁で割り切れる数値の一覧:
100 101 102 104 105 110 111 112 115 120 122 124 126 128 132 135 140 144 150 155 162 168 175 184 200

プログラムで使用しているアプローチ

• 整数型の範囲変数 START と END を受け取ります。
• 関数 divisiblebyDigits(int start, int end) が範囲を受け取り、「0以外のすべての桁で割り切れる数値の個数」を返します。
• 条件を満たす数値を数えるため、変数 count を 0 で初期化します。
• 判定用のフラグとして、変数 flag を用意します。
• forループで i = start から i = end まで、範囲内の数値を順に走査します。
• 各数値 num = i に対して、whileループで num > 0 の間、以下の処理を繰り返します。
• 桁 digit = num % 10 を求めます。digit > 0 かつ i % digit == 0 であれば flag = 1 を設定し、そうでなければ flag = 0 として break します。その後 num = num / 10 として次の桁を調べます。
• すべての0以外の桁が i を割り切れた場合、flag は 1 のまま残るため、count をインクリメントします。
• すべてのループが終了した時点で、count には条件を満たす数値の総数が格納されています。
• 最後に count を結果として返します。

なお、計算量は範囲内の数値の個数を N、1つの数値の桁数を D とすると O(N × D) となり、非常に効率的な全探索手法です。

サンプルコード（C++）

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

// 0以外のすべての桁で割り切れる数値の個数を返す関数
int divisiblebyDigits(int start, int end){
    int count = 0;
    int flag = 0;
    for (int i = start; i <= end; i++){
        int num = i;
        while (num > 0){
            int digit = num % 10;
            if (digit > 0){
                if (i % digit == 0)
                    flag = 1;   // 割り切れたのでフラグを立てる
                else{
                    flag = 0;   // 割り切れないのでフラグを解除して中断
                    break;
                }
            }
            num = num / 10;
        }
        if (flag == 1){         // すべての0以外の桁で割り切れる場合
            count++;
            //cout << i << " ";
        }
    }
    return count;
}

int main(){
    int START = 10, END = 50;
    cout << "0以外のすべての桁で割り切れる数値の個数: " << divisiblebyDigits(START, END);
    return 0;
}

出力

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

0以外のすべての桁で割り切れる数値の個数: 14

この例では、範囲 [10, 50] 内に「0以外のすべての桁で割り切れる」という条件を満たす数値が14個存在することを示しています。範囲を変更すれば、任意の区間に対して同じロジックでカウントできます。