C++でmで割り切れ、偶数桁に数字dを持つ範囲内の数の個数を求める方法

整数の範囲[start, end]、除数として使う変数m、そして判定対象となる数字dが与えられたとき、その範囲内で「mで割り切れる」かつ「偶数桁の位置に数字dを持つ」数がいくつあるかを計算するのが本記事の課題です。

例

入力 − int start = 20, end = 50, d = 8, m = 4

出力 − 範囲内でmで割り切れ、偶数桁に数字dを持つ数の個数: 2

説明 − 範囲は20から50です。数字8を含む候補は28、38、48で、いずれも2桁目(偶数桁)に8があります。このうち4で割り切れるのは28と48であるため、個数は2となります。

入力 − int start = 10, end = 100, d = 6, m = 2

出力 − 範囲内でmで割り切れ、偶数桁に数字dを持つ数の個数: 8

説明 − 範囲は10から100です。数字6を含む数は16、26、36、46、56、66、76、86、96ですが、6や66のように6が奇数桁に現れるものは対象から除外します。残りの16、26、36、46、56、76、86、96はすべて2で割り切れるため、個数は8になります。

プログラムで用いる手法

本解法では、数値を1桁ずつ扱いながら条件を満たす組み合わせを数える「桁DP(デジット・ダイナミック・プログラミング)」の考え方を採用し、メモ化再帰によって効率よく計算を行います。

• startからendまでの整数範囲を用意し、変数dとmを宣言して値を入力します。その後、データを処理用の関数へ渡します。
• vector型の変数(ここではvecとします)を作成します。
• whileループを回し、val % 10 の値をvectorに追加しながら、valを val / 10 で更新することで各桁を取り出します。
• STLのreverse関数にvec.begin()とvec.end()を引数として渡して呼び出し、桁の並びを正順に整えます。
• memsetを使って配列の全要素を-1で初期化します。
• set_total(0, 0, 0, vec) を返します。この関数が、偶数桁にdを持ち、かつmで割り切れる数を判定します。
• set_total関数の内部処理は次のとおりです。
  • placeがvectorのサイズと一致した場合、tempが0であれば1を、そうでなければ0を返します。
  • arr[place][temp][val] が-1以外であれば、その値を返します(メモ化による高速化)。
  • place % 2 が1(奇数桁)の場合、valが0であれば、dがvec[place]より大きいときに0を返します。
  • 変数temp_2を宣言し、0で初期化します。
  • dがvec[place]より小さい場合、temp_2を1に設定します。
  • 変数temp_3を宣言し、set_total()を再帰呼び出しした結果を格納して、arr[place][temp][val] = temp_3 として返します。
  • 結果を保持する変数countを宣言します。
  • 変数set_limitを宣言し、valが1なら9、それ以外ならvec[place]を設定します。
  • iを0からset_limitまで動かすforループを開始し、iがdと等しい場合はcontinueでスキップします。
  • 変数temp_2を宣言し、valを代入します。
  • iがvec[place]より小さい場合、temp_2を1に設定します。
  • set_totalの再帰呼び出し結果をcountに加算していきます。
  • 最後に arr[place][temp][val] = count として返します。

コード例

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

int arr[20][20][2];
int d, m;

int set_total(int place, int temp, int val, vector < int > vec) {
    if (place == vec.size()) {
        if (temp == 0) {
            return 1;
        }
        return 0;
    }
    if (arr[place][temp][val] != -1) {
        return arr[place][temp][val];
    }
    if (place % 2) {
        if (val == 0) {
            if (d > vec[place]) {
                return 0;
            }
        }
        int temp_2 = val;
        if (d < vec[place]) {
            temp_2 = 1;
        }
        int temp_3 = set_total(place + 1, (10 * temp + d) % m, temp_2, vec);
        return arr[place][temp][val] = temp_3;
    }
    int count = 0;
    int set_limit = (val ? 9 : vec[place]);
    for (int i = 0; i <= set_limit; i++) {
        if (i == d) {
            continue;
        }
        int temp_2 = val;
        if (i < vec[place]) {
            temp_2 = 1;
        }
        count += set_total(place + 1, (10 * temp + i) % m, temp_2, vec);
    }
    return arr[place][temp][val] = count;
}

int divisible(int val) {
    vector < int > vec;
    while (val) {
        vec.push_back(val % 10);
        val = val / 10;
    }
    reverse(vec.begin(), vec.end());
    memset(arr, -1, sizeof(arr));
    return set_total(0, 0, 0, vec);
}
int main() {
    int start = 20, end = 50;
    d = 8, m = 4;
    int count = divisible(end) - divisible(start);
    cout << "Count of Numbers in a Range divisible by m and having digit d in even positions are: " << count;
    return 0;
}

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

出力

Count of Numbers in a Range divisible by m and having digit d in even positions are: 2