C++で指定された数値で割り切れるn桁の数をカウントする方法

本記事では、2つの値、すなわち桁数を表す d と除数となる num が与えられたとき、「d 桁の整数のうち num で割り切れるもの」がいくつ存在するかを求める方法を解説します。

たとえば d に 2 が入力された場合、まず対象となるのは 10〜99 のすべての2桁の整数です。その中から num で割り切れる数だけを抽出し、その個数を数えます。

具体例を見てみましょう。

例1

• 入力: digit = 2, num = 12
• 出力: 指定された数値で割り切れるn桁の数の個数：8

説明： 12で割り切れる2桁の整数は、12, 24, 36, 48, 60, 72, 84, 96 の8個です。

例2

• 入力: digit = 2, num = 9
• 出力: 指定された数値で割り切れるn桁の数の個数：10

説明： 9で割り切れる2桁の整数は、18, 27, 36, 45, 54, 63, 72, 81, 90, 99 の10個です。

アルゴリズムの考え方

この問題は、すべての数を順番に調べることなく、数学的な計算だけで効率よく答えを求められます。手順は以下のとおりです。

• 桁数 digit と除数 num を入力として受け取ります。
• 該当する数の個数を格納する変数 count を 0 で初期化します。
• digi_first を pow(10, digit - 1)、つまり指定桁数の最小値（例：digit=2 なら 10）に設定します。
• digi_last を pow(10, digit)、つまり指定桁数の上限（例：digit=2 なら 100）に設定します。
• d_first を digi_first % num、d_last を digi_last % num として計算します。これは範囲の端点を num の倍数に調整するためです。
• digi_first を (digi_first - d_first) + num に更新し、範囲内で num で割り切れる最小の数を求めます。同様に digi_last を digi_last - d_last に更新し、範囲内で num で割り切れる最大の数を求めます。
• count を ((digi_last - digi_first) / num + 1) として計算します。これは等差数列の個数を求める式です。
• count を返して出力します。

この手法ではループ処理を使わないため、桁数が大きくなっても一定時間（O(1)）で結果を得られる点が大きなメリットです。

C++での実装例

#include <cmath>
#include <iostream>
using namespace std;
int main(){
    int digit = 2 , num = 9;
    // 個数を格納する変数
    int count= 0 ;
    int digi_first = pow(10, digit - 1);
    int digi_last = pow(10, digit);
    int d_first = digi_first % num;
    int d_last = digi_last % num;
    digi_first = (digi_first - d_first) + num;
    digi_last = digi_last - d_last;
    count = ((digi_last - digi_first) / num + 1);
    cout<<"指定された数値で割り切れるn桁の数の個数: "<<count<<"\n";
    return 0;
}

実行結果

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

指定された数値で割り切れるn桁の数の個数: 10

このように、剰余演算を活用して範囲の両端を num の倍数へ補正することで、繰り返し処理なしに「n桁のうち num で割り切れる数の個数」を高速に求めることができます。